LeetCode 92. Reverse LinkedList II

Question

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Explanation

这道题就是将m到n范围内的链表翻转。注意三个点，一个pre，一个curr，一个next。好搞啊..

Code

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        //Find m node
        for (int i=1; i< m; i++) {
            pre = pre.next;
        }
        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5

        ListNode start = pre.next;
        ListNode curr = start.next;
        for (int i=m; i<n; i++) {
            ListNode next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
            start.next = next;
            curr = next;
        }

        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
        return dummy.next;

    }
}

``