2021/2/16 链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

1. 用快慢指针解决问题，如上图，红色是慢指针走的路程，蓝色是快指针走的路程。快指针每次走两步，慢指针每次走一步。
2. 当慢指针走到入口节点时，路程为X，因为快指针每次走慢指针的两倍，所以快指针路程为2X。
3. 当他们相遇时，慢指针又走了Y，快指针则又走了2Y。
4. 根据上图我们可以得知，当慢指针走到入口节点时，快指针与慢指针的短弧距离为 ，长弧距离为 。
5. 当快慢指针相遇时，它们与入口节点的长弧距离为 ，也就是说只要让快指针回到起点，慢指针不动，然后它们每次只走 1 步，它们必定会在 X 步后相遇，这个位置正是入口节点。

Java代码实现

public class Solution {

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