141. Linked List Cycle

链表问题之环，第一道题是判断是否有环，第二道题是找出环的入口节点，第三道题是用第二道题的方法解决问题，第四道题就是简单的链表问题（用以巩固链表）。

Given a linked list, determine if it has a cycle in it.
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

[leetcode 141] Linked List Cycle

第一道题是判断是否有环，用两个指针，一个指针每次走一步，一个指针每次走两步，然后比较它们指向的元素是否相等；为什么可以这样做，因为如果有环，快指针就会在慢指针的后面，而它们的距离经过若干步都可以达到快指针指向第i个元素，慢指针指向第i+1个元素，这样下一步（快指针走两步后，慢指针走一步后）它们就会相遇

public boolean hasCycle(ListNode head) {
    ListNode p1,p2;
    p1=p2=head;
    while (p1!=null&&p1.next!=null){
        p1=p1.next.next;
        p2=p2.next;
        if(p1==p2)return true;
    }
    return false;
}

[leetcode 142] Linked List Cycle II

第二道题是上道题的延生，具体的可以看剑指offer，这里我们同样用一个快指针和一个慢指针，快指针走两步，慢指针走一步，如果有环，就会相遇；这里用 $s_{1}$ 表示快指针走过的节点个数，用 $s_{2}$ 表示慢指针走过的节点个数，用 $l$ 表示环中节点个数，用 $l_{0}$ 表示环的入口节点到快指针和慢指针相遇时的节点之间的节点个数，有如下公式：
其中k表示的是相遇时快指针已经在环上转过的圈数

$s_{1}=s_{2}+kl\\ s_{1}=2s_{2}$

由上面的公式可以得到： $s_{2}=kl$
现在让慢指针(记为p1)继续走，而让快指针回到头结点(记为p2)，并以慢指针的速度同速前进，相遇节点即为环的入口节点，证明如下：
此时的p2所走过的节点数为 $s_{2}-l_{0}$ ，而又有 $s_{2}=kl$ ，即走过的节点为 $kl-l_{0}$ ，慢指针p1在原先相遇的节点开始走，每次到达环入口所走的距离为 $ml-l_{0}$ ，显然这两个值是相等的（相减后对l取余），那么就说明必然会在环入口处相遇

public ListNode detectCycle(ListNode head) {
    ListNode p1,p2;
    p1=p2=head;
    while (p1!=null&&p1.next!=null){
        p1=p1.next.next;
        p2=p2.next;
        if(p1==p2)break;
    }
    if(p1==null||p1.next==null)return null;
    p1=head;
    while (p1!=p2){
        p1=p1.next;
        p2=p2.next;
    }
    return p1;
}

[leetcode 287] Find the Duplicate Number

这道题用环的解法可以说是我见到最激动的方法了，见My easy understood solution with O(n) time and O(1) space without modifying the array
大小为n+1的数组中只有一个重复的数字，而且这些数字均在1~n之间，这个重复的数字可能出现多次，上面的解法中用环的思想原理是，环中下一个节点是当前节点值对应的下标在数组中的值，那么如果数组中出现了重复的数，一定会有两次指向同一个节点，这样就形成了一个环，而该环的入口节点的下标就是重复的数字，我举个例子：

3  4  2  1  1
0  1  2  3  4
如上所示，第一行代表数组的值，第二行代表对应的下标，
也就是值的最大值是永远小于等于下标的最大值的(因为有重复的)
值3为第一个节点；第二个节点为下标为3的数组值，即1；第三个节点是下标为1的数组值，即4；
第4个节点为下标为4的数组值，即1；现在的1出现了两次，即形成了环，此时便会指向第三个节点4，也就是环的入口节点，而其下标就是重复的数

代码就是第二道题的代码，主要是上面的思路，代码如下：

public int findDuplicate(int[] nums) {
    if(nums.length<=1)return -1;
    int slow,fast;
    slow=nums[0];
    fast=nums[slow];
    while (slow!=fast){
        slow=nums[slow];
        fast=nums[nums[fast]];
    }
    fast=0;
    while (fast!=slow){
        fast=nums[fast];
        slow=nums[slow];
    }
    return slow;
}

上面这个方法也不是一般人能想到的，此题总会有个一般的解法吧，见disscuss上排第二的解法，用的是二叉查找，取1~n的中间数mid，判断数组中的数小于mid的个数是否大于mid，如果大于，说明重复的数一定在1~mid中，如果小于，说明重复的数在(mid+1)~n之间，继续选取mid，直到只有一个数为止。具体的代码就不详述了，见Two Solutions (with explanation)

[leetcode 143] Reorder List

这道题倒不是难，思路很清楚，就是写着很复杂，要考虑几种情况
先找到链表的中间节点，然后将中间节点前面的一个节点的next指向null，将从中间节点到尾节点的链表反转，将这两个链表拼接起来，还要考虑第二个链表可能会比第一个链表多一个元素的情况

public static void reorderList(ListNode head) {
    if(head==null||head.next==null||head.next.next==null)return;
    int n,m;
    n=m=0;
    ListNode p,p2,q,q2,pre;
    p=p2=head;
    while (p!=null){
        n++;
        p=p.next;
    }
    n/=2;
    pre=head;
    while ((++m)<=n){
        pre=p2;
        p2=p2.next;
    }
    pre.next=null;
    p=p2;
    q=p.next;
    p.next=null;
    while (q!=null){
        q2=q.next;
        q.next=p;
        p=q;
        q=q2;
    }
    q=head;
    while (p!=null&&q!=null){
        p2=p.next;
        q2=q.next;
        q.next=p;
        if(q2!=null)p.next=q2;
        p=p2;
        q=q2;
    }
}