Problem

Reverse a linked list from position m to n.

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

Example
Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

思路

• 重要条件: 1 ≤ m ≤ n ≤ length of list

• 需要先找到第m - 1个点

• 然后用 一 中的方法去反转 m ~ n 的点, curt指针会落到第n + 1个点, prev指针会落到第n个点

    public ListNode reverseBetween(ListNode head, int m , int n) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;

        // find the m - 1 node
        for (int i = 1; i < m; i++) {
            if (node == null) {
                return node;
            }
            node = node.next;
        }

        ListNode mNode = node.next;
        ListNode prev = mNode;
        ListNode curt = mNode.next;

        // reverse 
        for (int i = m; i < n; i++) {
            if (curt != null) {
                ListNode temp = curt.next;
                curt.next = prev;
                prev = curt;
                curt = temp;
            }    
        }

        // connect
        node.next = prev;
        mNode.next = curt;

        return dummy.next;

    }