链表中环的入口结点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

解题思路

两个结点同时运行，其中快结点 fast 一次走两个结点，慢结点 slow 一次走一个结点。

假设 x 为环前面的路程（黑色路程），a 为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c 为环的长度（蓝色 + 橙色路程）

两结点相遇时，快结点走过的路程：

L_f=x+n*c+a

慢节点走过的路程：

L_s=x+m*c+a

且速度 fast 是 slow 的二倍，所以：

L_f=2L_s

于是，可以推出：

x=(n-2*m)*c-a=(n-2*m-1)*c+c-a

也就是说，环前面的路程=环长度的整数倍 +c-a。
而 c-a 就是橙色部分，也就是从起点走到入口点的路程相当于走几个环 + 橙色部分的路径。
那么我们让 slow 在相遇点走，fast 在起始点走(一次只走一个结点)，最后一定是在环的入口相遇。

时间复杂度：O(n)

空间复杂度：O(1)

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null || pHead.next.next == null)
            return null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        
        while (fast != slow) {
            if (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else
                return null;
        }
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}