92. Reverse Linked List II

# Medium

Key idea: record pre-node of start, reverse from start to end, record successor of end, link pre-node and successor

核心： 记录第（m-1）个点，反转第m~n个点，记录第（n+1）个点，连接第（m-1）和（n+1）两个点

process of reverse part of a linked list

Solution:

1. Record (m-1) element

2. Reverse from m to n

3. Record (n+1) element

4. Correctly link (m-1) to nth and link mth to (n+1)

5. 记录第(m-1)个元素

6. 反转第m到第n个元素

7. 记录第(n+1)个元素

8. 连接(m-1)到n，连接m到(n+1)

Java(O(n))

refer to #206.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == right) return head;
        
        // find the Node just before left
        ListNode dump = new ListNode();
        dump.next = head;
        ListNode pre = new ListNode();
        pre = dump;
        for(int i = 1; i < left; i ++) {
            head = head.next;
            pre = pre.next;
        }
        
        // reverse [left, right]
        ListNode start = head, preNode = head;
        head = head.next;
        for(int i = left; i < right; i ++) {
            ListNode tempNode = head.next;
            head.next = preNode;
            preNode = head;
            head = tempNode;
        }
        
        // connect pre -> reverse -> tail
        pre.next = preNode;
        start.next = head;
        return dump.next;
    }
}

Python