链表中环的起点 Linked List Cycle II

问题：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

解决：

① 使用快慢指针，记录两个指针相遇的位置，当两个指针相遇了后，让其一指针从链表头开始向后走，另一个从相遇的点开始，此时再相遇的位置就是链表中环的起始位置。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution { //2ms
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//有环
                break;
            }
        }
        if (fast == null || fast.next == null) {//不存在环
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

② 进化版

public class Solution { //1ms
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast && slow != null) {
                ListNode slow2 = head;
                while (slow != slow2) {
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }
}

【总结】链表找环方法证明 http://www.cnblogs.com/wuyuegb2312/p/3183214.html

一： 判断两个链表是否相交，假设两个链表不带环。https://my.oschina.net/liyurong/blog/994540

解决方法：用指针p1、p2分别指向两个链表头，不断后移；最后到达各自表尾时，若p1==p2，那么两个链表必相交。

二： 如果链表可能有环，上面的方法怎么调整？

分情况讨论：
如果两个链表都没有环，那么同原算法；
如果两个链表一个有环，一个没环，那么必然不相交。
(*)如果两个链表都有环，判断一个链表环上的任一点是否在另一个链表上，如果是，则必相交，反之不相交。这时，需要找到另一个链表完整的环都包括了哪些结点，才能进行判断。(*)
可以看出，解答这个问题重点在于判断是否有环。

三： 如果必须要求出两个链表相交的第一个节点呢？

（*）    思路：如果两个尾结点是一样的，说明它们有重合；否则两个链表没有公共的结点。
    在上面的思路中，顺序遍历两个链表到尾结点的时候，我们不能保证在两个链表上同时到达尾结点。这是因为两个链表不一定长度一样。但如果假设一个链表比另一个长L个结点，我们先在长的链表上遍历L个结点，之后再同步遍历，这个时候我们就能保证同时到达最后一个结点了。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的。因此，它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。
    在这个思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历若干次之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。PS：没有处理一种特殊情况：就是一个是循环链表，而另一个也是，只是头结点所在位置不一样。 （*）
    对于特殊情况，相交的第一个结点可以是第一个链表的表头，也可以是第二个链表的表头。因为从表头开始二者就开始相交了。对于这种情况，如果判断出二者都是循环链表，就可以直接返回其中之一的头指针。

四： 求链表倒数第k个结点

(*)设置两个指针p1,p2，首先p1和p2都指向head，然后p2向前走k步，这样p1和p2之间就间隔k个节点，最后p1和p2同时向前移动，直至p2走到链表末尾。(*)

【总结】现在来看，遗留问题是：

1.如何判断链表有环？

2.如何找到链表环的入口？

简单来说就是：

1. 对于问题1，指针p1、p2指向表头，每次循环p1指向后继，p2指向后继的后继；循环的结束条件是，p2后继为空（无环）或p1==p2（有环）。

下面用易于理解的方式证明，这个解法中如果有环，p1和p2必同时在停留在某个节点。

如左图，在任意时刻，p1和p2都在环上。由于p1每次向前1步，p2每次向前两步，用相对运动的观点来看，把p1看作静止，那么p2每次相对p1向前1步，二者在顺时针方向上的距离每经过一个时刻就减少1，直到变为0，也即二者恰好相遇。这样就证明了在离散情况下，对于有环链表，二者也是必然在某一时刻相遇在某个节点上的。

2. 对于问题2寻找环的入口问题。

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

【总结】寻找环存在和环入口的方法：

用两个指针p1、p2指向表头，每次循环时p1指向它的后继，p2指向它后继的后继。若p2的后继为NULL，表明链表没有环；否则有环且p1==p2时循环可以终止。此时为了寻找环的入口，将p1重新指向表头且仍然每次循环都指向后继，p2每次也指向后继。当p1与p2再次相等时，相等点就是环的入口。