环形链表 II

难度: Medium

给定一个链表，返回链表开始入环的第一个节点。从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10⁴] 内
-10⁵ <= Node.val <= 10⁵
pos 的值为 -1 或者链表中的一个有效索引

进阶：是否可以使用 O(1) 空间解决此题？

注意：本题与主站 142 题相同： https://leetcode-cn.com/problems/linked-list-cycle-ii/

Submission

运行时间: 30 ms

内存: 18.3 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        def checkCycle(root):
            fast = root
            slow = root

            while fast is not None and fast.next is not None:
                fast = fast.next.next
                slow = slow.next
                if slow == fast:
                    return slow
            return None

        nodeInCycle = checkCycle(head)

        if nodeInCycle is None:
            return None

        first = nodeInCycle
        second = head

        while first != second:
            first = first.next
            second = second.next

        return second

Explain

此题解使用了快慢指针的方法来确定链表中是否有环，并找出环的入口。首先，定义两个指针，快指针每次移动两步，慢指针每次移动一步。如果链表中有环，快慢指针最终会在环内相遇。相遇后，将其中一个指针移动到链表的头部，然后两个指针都每次仅移动一步，当它们再次相遇时，相遇点即为环的入口。这个方法有效利用了数学上的环和链表结构的特性，通过两次遍历来定位环的入口。

时间复杂度: O(n)

空间复杂度: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        def checkCycle(root):
            fast = root
            slow = root

            # 快慢指针判断链表中是否存在环
            while fast is not None and fast.next is not None:
                fast = fast.next.next
                slow = slow.next
                if slow == fast:
                    return slow
            return None

        nodeInCycle = checkCycle(head)

        if nodeInCycle is None:
            return None

        first = nodeInCycle
        second = head

        # 让一个指针从环内相遇点开始，另一个从头开始，两者速度相同，再次相遇点即环入口
        while first != second:
            first = first.next
            second = second.next

        return second

Explore

当快慢指针在环中相遇后，说明链表确实存在环。此时，从链表头部到环入口的距离设为D，环入口到快慢指针相遇点的距离设为S，环的剩余长度设为R。在快慢指针相遇时，慢指针走过的总距离为D + S，而快指针则是D + S + n(S + R)，其中n是快指针比慢指针多绕环的圈数。由于快指针是慢指针速度的两倍，因此2(D + S) = D + S + n(S + R)。简化后得到D = n(S + R) - S = (n-1)S + nR。这表明从链表头部到环入口的距离D等于从相遇点绕环n-1圈后再走入环入口的距离。因此，将一个指针置于链表头部，另一个置于相遇点，然后两个指针以相同的速度前进，它们将在环的入口相遇。

快指针每次移动两步，而慢指针每次移动一步，不会导致快指针跳过环的入口或错过慢指针的相遇。尽管快指针移动得更快，但如果有环，快指针会在某个时间点从后面追上慢指针，因为它们都被限制在一个封闭的环中。快指针不可能跳过慢指针，因为它们每次移动的步伐是连续的。对于无环的情况，快指针的行为只会导致它更快地达到链表的尾部，并且不会影响算法的结果，因为它会在慢指针之前检测到链表的末端。

即使环的长度非常短，例如只有一个节点（即自环的情况），快慢指针法仍然有效。在这种情况下，快指针和慢指针会在环中的同一节点上相遇，因为快指针每次绕环跑两步，慢指针每次跑一步。如果存在这样一个节点使得节点的next指向自己，快指针和慢指针会在该节点上相遇，从而确认环的存在。