92.Reverse-Linked-List-II

92. Reverse Linked List II

题目地址

https://www.lintcode.com/problem/reverse-linked-list-ii/

https://leetcode.com/problems/reverse-linked-list-ii/

题目描述

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

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


}