Leetcode 92. Reverse Linked List II

Description

92. 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

Solution

1. 需要使用DummyHead，因为反转的起始点可能是第一个元素
2. 使用双指针确定反转的区间，找到idx m 前一个元素和 idx n后一个元素
3. 反转LinkedList可以将nex指针初始值赋为cur，这样每次反转之前先挪动nex到下一个位置，就不用考虑cur为null，移动nex所产生的NullPointerException了

    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(m == n)
                return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode slow = dummyHead;
            ListNode fast = dummyHead;
            //find the prev position of m and nex position of n
            for(int i = 0; i <= n - m + 1; i++ )
                fast = fast.next;

            for(int i = 1; i < m; i++){
                slow = slow.next;
                fast = fast.next;
            }

            ListNode cur = slow.next;
            ListNode nex = cur;
            ListNode prev = fast;

            while(cur != fast){
                nex = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nex;
            }

            slow.next = prev;

            return dummyHead.next;
        }
    }