leetcode142 环形链表2 形象解释

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

设快指针一次跳两下，慢指针一次跳一下。

大家可以把入环前的几个节点叠加到链表的节点上，就可以看得很清楚了。就像我们的塑胶跑道上正上方多出了一段距离。那么这几个节点的起始节点所叠加的那个点就是两个指针第一次相遇的点。

我们在快慢指针相遇时，让一个指针从链表起点开始走，一个指针从相遇点开始走，两者速度一样，这两个指针的相遇点就是入环的第一个节点。

或者这么想，开始后，慢指针走到环起点时，两者在环中的位置是不一样的（其速度不同）。
我们可以试着把两个指针都倒车，直到两者处于环中的同一位置（而不是环外的位置）。
这个位置其实就是它们相遇的位置。
那么如果倒车到环外呢？肯定是回到了链表的起点。

下面是双指针法的代码

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head,  slow = head; // 双方从都从头结点开始走
        while(true){
            if(fast == null || fast.next == null)return null; // 遇到null，说明没有环，直接返回。
            fast = fast.next.next; // 兔子是乌龟速度的两倍
            slow = slow.next; // 乌龟比兔子慢
            if(fast == slow)break; // 到达两者相遇点
        }
        fast = head; // 我们也不知道 a 到底是多少，继续利用双指针法
        while(slow != fast){
            // 两个指针速度相同，走过 a 个节点距离时相遇
            slow = slow.next;
            fast = fast.next;
        }
        // 循环停止时，两个指针走过了同样的距离，都到达了 s 节点
        return slow;
    }

类比可能不严谨，但大家理解就好。发现错误的帅哥靓女们请评论指出！