CC57 链表内指定区间反转

大致思路：1. 找到m位置 2. 在后续的遍历中对链表进行反向 3. 调整指针指向。
准备工作：设置一个哨兵i初始值为1，设置一个头结点first，值为1（防止第一个结点换到后面）。设置pre指针初始值为first，找到需要反转的区间前一个节点；last初始值为null，为cur当前节点的前一个节点；cur初始值为head，遍历链表节点；tmp为null，记录当前节点的下一个节点；将pre.next置为head。

1. 将pre.next = head;
2. 通过while遍历区间前的每一个节点并对i累加，直到m=i，在这个过程中，对tmp、pre、cur进行迭代，使得cur指向m时，可以直接开始后续的链表反向。
3. 将first.val 置为i，这个值用来判断pre是否发生移动。若未发生移动，pre依然等于first。
4. while循环对后续的链表进行反向（简单的指针移动），直到i等于n。
   5.由于前面的循环到n就停了，所以还需要进行最后一次指针移动。看代码细品。通过pre.next.next = tmp和 pre.next = cur对链表进行反向。最后根据pre的值判断pre是否发生移动，并返回对应值。

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head.next==null || m==n) return head;
        int i = 1;
        ListNode first = new ListNode(1);
        ListNode pre = first,last = null,cur = head,tmp = null;
        pre.next = head;
        while(i<m){
            tmp = cur.next;
            pre = cur;
            cur = cur.next;
            i++;
        }
        first.val = i;
        while(i<n){
            tmp = cur.next;
            cur.next = last;
            last = cur;
            cur = tmp;
            i++;
        }
        tmp = cur.next;
        pre.next.next = tmp;
        pre.next = cur;
        cur.next = last;
        if(pre.val==1) return first.next;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29