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.

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;

        for (int i = 0; i < m - 1; i++)

            pre = pre.next;

        

        ListNode start = pre.next;

        ListNode then = start.next;

        //pre=1,start = 2, then = 3

 

        for (int i = 0; i < n - m; i++) {

            start.next = then.next;//2->4

            then.next = pre.next;//3->2

            pre.next = then;//1->3

            then = start.next;//then等于4

        }

     //第一次reverse：1-3-2-4-5，pre=1， start=2，then=4

    //第二次reverse：1-4-3-2-5，

        return dummy.next;

    }

}