😀前言
在链表的操作中，环形链表是一个常见且需要特别处理的结构。当我们遇到一个包含环的链表时，如何找到环的入口结点是一个经典的问题。本文将详细介绍使用双指针技术来解决这一问题，并提供一个基于 Java 的实现代码。

😊链表中环的入口结点

NowCoder

😍题目描述

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

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

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

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

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

💞输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

💞返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

😋示例

示例1

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

示例2

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

示例3

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

😃解题思路

使用双指针，一个快指针 fast 每次移动两个节点，一个慢指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。

假设环入口节点为 y1，相遇所在节点为z1。

假设快指针 fast 在圈内绕了 N 圈，则总路径长度为 x+Ny+(N-1)z。z 为 (N-1)倍是因为快慢指针最后已经在z1 节点相遇了，后面就不需要再走了。

而慢指针slow总路径长度为x+y。

因为快指针是慢指针的两倍，因此 x+Ny+(N-1)z = 2(x+y)。

我们要找的是环入口节点y1，也可以看成寻找长度 x 的值，因此我们先将上面的等值分解为和 x 有关：x=(N-2)y+(N-1)z。

上面的等值没有很强的规律，但是我们可以发现 y+z就是圆环的总长度，因此我们将上面的等式再分解：x=(N-2)(y+z)+z。这个等式左边是从起点x1 到环入口节点 y1 的长度，而右边是在圆环中走过(N-2) 圈，再从相遇点z1 再走过长度为 z的长度。此时我们可以发现如果让两个指针同时从起点 x1和相遇点 z1开始，每次只走过一个距离，那么最后他们会在环入口节点相遇。

😀解题思路2

解决这个问题的关键在于如何有效地检测链表中的环，并找到环的入口结点。我们可以使用一种被称为快慢指针的技术来实现。

1. 快慢指针的移动： 我们设置两个指针 slow 和 fast，其中 slow 每次移动一个节点，而 fast 每次移动两个节点。如果链表中存在环，两个指针最终会在环内相遇。
2. 确定相遇点： 当 slow 和 fast 相遇时，说明链表中存在环。此时，fast 指针已经绕环走了一圈或多圈，而 slow 则走了半圈。
3. 找到环的入口： 相遇后，我们将 fast 指针移回链表头部，并让 slow 和 fast 同步移动，每次移动一个节点。最终，它们会在环的入口处相遇，此时的节点即为我们要找的环的入口结点。

💗代码实现

以下是基于上述思路的 Java 代码实现：

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 如果链表为空或只有一个节点，直接返回 null
        if (pHead == null || pHead.next == null)
            return null;

        // 初始化慢指针 slow 和快指针 fast
        ListNode slow = pHead, fast = pHead;

        // 使用 do-while 循环来保证 slow 和 fast 至少移动一次
        do {
            // 快指针每次移动两步，慢指针每次移动一步
            fast = fast.next.next;
            slow = slow.next;
        } while (slow != fast);  // 直到两个指针相遇

        // 将快指针移回链表头部
        fast = pHead;

        // 快慢指针同时移动，直到相遇在环的入口处
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 返回相遇的节点，即环的入口节点
        return slow;
    }
}

💕性能分析

该算法的时间复杂度为 O(n)，因为无论链表长度如何，slow 和 fast 最多只需要遍历链表两次。空间复杂度为 O(1)，因为我们只使用了两个额外的指针，没有占用额外的存储空间。

💕原理解析

在这段代码中，我们首先通过快慢指针的相遇来判断链表是否存在环。当我们确定存在环时，将 fast 指针移回链表头部，并再次与 slow 同步移动。在它们相遇的地方，即是环的入口结点。这种方法利用了快慢指针的速度差和链表的结构特性，能够高效地找到环的入口。

😄总结

通过使用快慢指针技术，我们可以高效地检测链表中的环，并找到环的入口结点。这种方法简单明了，同时具备良好的时间和空间复杂度表现。在处理链表相关问题时，快慢指针是一种非常实用的工具，希望本文的讲解能够帮助你更好地理解和解决链表中的环问题。