Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode premNode = dummy;
for (int i = 1; i < m; i++) {
premNode = premNode.next;
}
ListNode prev = null, curr = premNode.next;
while (curr != null && m <= n) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
m++;
}
premNode.next.next = curr; // premNode.next.next => m Node
premNode.next = prev; // prev: n, curr: n+1
return dummy.next;
}
}
class Solution {
// Object level variables since we need the changes
// to persist across recursive calls and Java is pass by value.
private boolean stop;
private ListNode left;
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
this.recurseAndReverse(head, m, n);
return head;
}
public void recurseAndReverse(ListNode right, int m, int n) {
// base case. Don't proceed any further
if (n == 1) {
return;
}
// Keep moving the right pointer one step forward until (n == 1)
right = right.next;
// Keep moving left pointer to the right until we reach the proper node
// from where the reversal is to start.
if (m > 1) {
this.left = this.left.next;
}
// Recurse with m and n reduced.
this.recurseAndReverse(right, m - 1, n - 1);
// In case both the pointers cross each other or become equal, we
// stop i.e. don't swap data any further. We are done reversing at this
// point.
if (this.left == right || right.next == this.left) {
this.stop = true;
}
// Until the boolean stop is false, swap data between the two pointers
if (!this.stop) {
int t = this.left.val;
this.left.val = right.val;
right.val = t;
// Move left one step to the right.
// The right pointer moves one step back via backtracking.
this.left = this.left.next;
}
}
}