#LeetCode 142 Linked List Cycle

先参考第141题，判断链表中是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode walk = head;
        ListNode run = head;
        while(run.next!=null && run.next.next!=null){
            walk = walk.next;
            run = run.next.next;
            if(walk==run) return true;
        }
        return false;
    }
}

整体思路为，有两个指针，一个每次走一步，一个每次走两步，如果最后两个指针能相遇，则肯定在链表中存在环，先不管他们各自绕了多少圈。
再看142题，不止要判断是否有环，还要返回环开始的节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode walk = head;
        ListNode run = head;
        while(run.next!=null && run.next.next!=null){
            walk = walk.next;
            run = run.next.next;
            if(walk==run){
                ListNode slow = head;
                while(slow!=walk){
                    slow = slow.next;
                    walk = walk.next;
                }
                return slow;
            }
        }
        return null;
    }
}

先看代码，整体思路跟141题差不多，只是在判断出有环后，还要进行一步操作，这步操作的意思如下。
假设两个指针，run和walk，

假设walk走了
A+B步（A为从头节点走到环开始的距离，B为在环内走的距离）

那么run走了2(A+B)步,因为run每次走两步

设环长为N
则

A+B+N=2A+2B
N=A+B

此时再增加一个从头开始走的指针，slow，他走到环的距离为A，那么，slow走了A步，walk走了A+B+A步，又引文N=A+B，那么slow和walk肯定会汇合在A处，即他们相遇的地方即为环开始的地方。