Reverse Linked List II

LintCode LeetCode

这道题一开始卡在了不知道怎么保留开始reverse的节点前面那个节点，因为最后reverse完了得用到它。发现自己一直在移动那个节点的reference，导致最后没办法连结逆转完之后的节点。

后来想明白了（参考了答案），一开始记录下来的开始reverse的前一个点nodePrem, 要一直不动。参与reverse的点才需要动。
这样我们就需要写下四个点：
nodePrem;
nodem;
noden（prev);
nodenplus(curt)

其中nodePrem, nodem是不能动的，因为我们最后reverse完了需要用他们来衔接。注意到这里的prev是从nodem开始的，而不是nodePrem。记住prev,curt是要参与遍历的点，它不可能从一个我们需要保持不动的点开始（比如这里的nodePrem). 而且一定要记得：动的是prev,不是nodem. 我们可以把这里的prev, curt看作是noden, nodenplus.这是可以的，因为通过遍历我们可以到达noden, nodenplus的真实位置。

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        for (int i = 1; i < m; i++){
            if (head == null){
                return null;
            }
            head = head.next;
        }
        /**
         * We need to record four points:(or three because noden and nodem starts the same)
         * 
         * 1. nodePrem : the point before the one who needs to be reversed in the original list (remain the same)
         * 2. nodem: the first node to be reversed in the original list. (stay the same)
         * the above two are used to link the reversed list in the end.
         * 
         * 3. noden: the second node to be reversed. (increase)
         * 4. nodePostn : the node after the last node to be reversed in the original list
         * (increase)
         * the above two are used during the reverse process.
         * 
         *
         */
        ListNode nodePrem = head;
        ListNode nodem = head.next;
        ListNode noden = nodem;
        ListNode nodePostn = noden.next;
        for (int i = m; i < n; i++){
            ListNode temp = nodePostn.next;
            nodePostn.next = noden;
            noden = nodePostn;
            nodePostn = temp;
        }
        nodePrem.next = noden;
        nodem.next = nodePostn;
        return dummy.next;
    }
}