【算法手记03】反转链表

public ListNode reverseList(ListNode head) {  
    ListNode cur = head;  
    ListNode dummy = new ListNode();  
    while (cur!=null){  
        ListNode next = cur.next;  
        //先接管后继  
        cur.next = dummy.next;  
        //再接入前驱  
        dummy.next = cur;  
        cur = next;  
    }  
    return dummy.next;  
}

直接操作原链表实现

此方法不引入新链表，空间复杂度更低，但也更复杂。

先画出初始和结束的状态：

下图中，cur作为遍历链表指针，同上。

随后，cur的next指向它的前一个结点prev。初始时，prev为null。随后，prev、cur依次向后移1位。

当cur指向null时，prev指向链表末尾，此时反转完毕，循环跳出。

代码如下：

ListNode prev = null;  
ListNode cur = head;  
while (cur!=null){  
    ListNode next = cur.next;  
    cur.next = prev;  
    prev = cur;  
    cur = next;  
}  
return prev;

指定区间反转

lc92

本题与lc206反转整个链表的实现方法是类似的。

在lc206中，我们将遍历到的原链表的结点依次插到dummy结点的后面，那么本题我们只需要将遍历到的区间节点依次插入到反转区间的第一个位置，也就是反转区间的前驱结点之后即可。

本题指针较多，写题的时候一定要画图，不然很容易把自己搞乱。

过程如下：

下面来考虑具体细节。我们选取反转区间中间的一部分来讨论实现细节。

如下图。由上面可以知道，cur指针每往前走一步，都要把自身插到pre结点之后。

类似这种更换链表中指定结点的位置的需求，我们一定要确定好结点的前驱和后继，以便它变换位置后，其他顺序不变。

明白这点之后，开始操作，将cur插入pre之后。

1. 插入结点操作遵循 “先接管后继，再接入前驱” 原则，cur先将其next指针指向pre的next，随后pre的next指针指向cur。
2. front的next指针指向next，cur指针移向next，大功告成。

   

   

随后考虑初始化条件。front最开始应该和cur同时指向pre.next。

这是因为，按照上面的方法，第一个节点cur.next指向pre.next时，出现自环。

front指向next时，链表恢复正常。由此可见front最开始应该和cur指向同一个位置。第二次移动之后，cur都会移向next，而front不会变。

实际上，front指针永远指向原区间的第一个结点。

再考虑边界条件。

1. 由题中所给的变量范围可知，链表至少会有一个结点、left一定不会大于right，因此非法输入不需要考虑。
2. 考虑指针越界。当right=n也就是区间到链表末尾时，当cur移动到right处，其next为null，不会触发空指针异常。

   综上，本题不需要额外考虑边界条件。

想好后，代码就很好写了。

public ListNode reverseBetween(ListNode head, int left, int right) {  
    ListNode dummy = new ListNode();  
    dummy.next = head;  
    int cnt = 1;  
    ListNode pre = dummy,cur,front;  
    while (cnt  
        cnt++;  
        pre = pre.next;  
    }  
    cur = pre.next;  
    front = cur;  
  
    while (cnt  
        ListNode next = cur.next;  
        cur.next = pre.next;  
        pre.next = cur;  
        front.next = next;  
        cur = next;  
        cnt++;  
    }  
    return dummy.next;  
  
}
  
    ListNode dummy = new ListNode();  
    dummy.next = head;  
    ListNode cur = head;  
    int len = 0;  
    while (cur!=null){  
        len++;  
        cur = cur.next;  
    }  
    int groupCnt = len/k;  
    ListNode pre = dummy;  
    cur = pre.next;  
    ListNode front = pre.next;  
    for(int i = 0;i