LeetCode 环形链表 II 以及 链表是否有环 详解原理

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

设：起点为A，第一个入环的点为B；

设有两个人，其中slower的速度是1，faster的速度为2，相遇点为C，环长度为L = L' - BC

则有 (AB +  BC ) / 1 = (AB + BC + nL) / 2

2(AB + BC) = AB + BC + n(BC + L')

AB + BC = n(BC + L')

AB = (n - 1)(BC + L') + L'

AB = (n-1)L + L'

也就是说，如果有两个相同速度的人，分别从A点和C点出发，则会在B点相遇

根据上述的证明：

可以得到下面的答案

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean meet = false;
        while(slow != null && fast != null){
            if(slow.next == null) break;
            slow = slow.next;
            if(fast.next == null || fast.next.next == null) break;
            fast = fast.next.next;
            if(slow == fast){
                meet = true;
                break;
            }
        }
        ListNode p = head;
        while(meet && p != slow){
            p = p.next;
            slow = slow.next;
        }
        if(meet){
            return p;
        }else{
            return null;
        }
    }
}