## ้ข็ฎๆ่ฟฐ

``````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``````

## ไปฃ็ 

### Approach #1 Iteration

``````public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);

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;
}
}``````

### Approach #2 Recursion

``````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.stop = false;
}

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;
}
}

}``````

Last updated