reverse Linked List II

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.

旋转链表中的部分节点。只能遍历一次链表（从头到尾遍历完算一次）。

仔细观察上面的例子，从原始到最后结果可以看成经历两步（n-m），第一步将3插入到2前面（1后面），变成1,3,2,4,5.第二次将4插入到3前面（1后面），变成1,4,3,2,5。

经过上面分析，我们发现，只要从第一个旋转点后面开始，依次将节点插入到1后面（第一个旋转点前面的节点，该节点不变）。观察上面解析，每次要插入到1后面的元素都是2的下一个元素。所以我们用pre和start变量表示1和2（m-1个节点和m个节点），并且这两个变量是不变的，然后依次将start的下一个变量插入到pre后面就行。因为头结点也可能发生变化，所以新建一个节点dummy指向头结点。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null||head.next==null||m==n) return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
        for(int i=0;i<m-1;i++) pre=pre.next;//移动到m-1的位置。旋转点前面
        ListNode start=pre.next; //开始的旋转节点
        ListNode then=start.next;//下一个要插入到pre后面的节点
        //1,2,3,4,5  m=2,n=4.pre=1,start=2,then=3,一开始将3插入到1后面，也就是将2的next指向4，将3断开，然后插入。这里要变的只有then节点，因为他是start的下一个要插入的点
        //进行n-m次插入,
        for(int i=0;i<n-m;i++){
            start.next=then.next;//断开要插入到前面的节点then.
            //插入
            then.next=pre.next;//这里不能等于start，因为start不变一直是2，会往后移的。
            pre.next=then;
            //then设置为下一个要插入元素
            then=start.next;
        }
        return dummy.next;
    }
}