题目描述

给一个长度为 n 的链表，若其中包含环，请找出该链表的环的入口结点，否则，返回 null。

数据范围： nle10000n≤10000，1<=结点值<=100001<=结点值<=10000

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

• 输入描述：输入分为 2 段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
• 返回值描述：返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例

// 输入
{1,2},{3,4,5}
// 返回值
// 返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即 3
3

// 输入
{1},{}
// 返回值
// 没有环，返回对应编程语言的空结点，后台程序会打印"null"
"null"

// 输入
{},{2}
// 返回值
// 环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即 2
2

解题思路

快慢指针法：

快慢指针可以很容易判断一条链表是否存在环，快指针 fast 每次走两步，慢指针 slow 每次走一步，那么若进入环中，每次他们之间的相对距离都会 -1，直到两者相遇。

那么，怎么使用快慢指针找到环的入口呢？

在慢指针 slow 进入链表环之前，快指针 fast 已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针（第一次相遇）

假设：fast 指针在环中走了 n 圈，slow 指针在环中走了 m 圈时，两指针相遇。环前距离为 x，入口节点到第一次相遇节点相差距离为 y，相遇节点到环入口为距离为 z。则有：

• x + n * (y + z) + y（fast 指针第一次相遇步数）
• x + m * (y + z) + y（slow 指针第一次相遇步数）
• 则：x + n (y + z) + y = 2 (x + m * (y + z) + y)
• 得：x + y = (n − 2m)(y + z)
• 即：从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小
• 那如果 fast 指针从头开始遍历到相遇位置，slow 指针从相遇位置开始在环中遍历，使用相同的步数，最后会在 y 节点处相遇，由于步数相同，所以在环入口处已经相遇，y处属于重复相遇。

示例：

输入：{1,2},{3,4,5}
fast 每次走 2 步，slow 每次走 1 步，第一次相遇
fast：3 -> 5 -> 4
slow：2 -> 3 -> 4

令快指针 fast 为 head，这时快慢指针同时一步一步走
fast：2 -> 3
slow：5 -> 3
再次相遇节点 3 即为入口节点

因此，可以得出结论：

快指针 fast 每次走两步，慢指针 slow 每次走一步，第一次相遇后，令快指针 fast 为 head，这时快慢指针同时一步一步走，再次相遇点即为环的入口

代码实现

/**
 * [JZ23-中等]链表中环的入口结点
 *
 * @param pHead Node类
 * @return Node类
 */
func entryNodeOfLoop(pHead *Node) *Node {
    if nil == pHead || nil == pHead.Next {
        return nil
    }
    fast, slow := pHead, pHead
    for nil != fast && nil != fast.Next.Next {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            fast = pHead
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return fast
        }
    }
    return nil
}