当前位置：首页 > news >正文

LeetCode 142：环形链表 II | 双指针检测与定位详解

news 2026/5/22 2:05:11

LeetCode 142：环形链表 II | 双指针检测与定位详解

引言

环形链表 II（Linked List Cycle II）是 LeetCode 第 142 题，难度为 Medium，是环形链表问题的进阶版本。继判断链表中是否存在环之后，这道题进一步要求找出环的入口节点，即从哪个节点开始链表进入了循环。这个问题不仅考察对双指针技巧的掌握，还需要一定的数学推导能力来理解为什么双指针能够找到环的入口。

在链表相关问题中，环的检测和定位是一个重要的主题。环的存在可能导致程序陷入无限循环，因此在实际工程中，检测链表是否存在环是重要的安全检查。而找到环的入口位置则可以帮助我们了解环的结构，为后续处理（如打破环、计算环长度等）提供基础。本文将深入分析 Floyd 双指针算法的原理，并提供多种解法的对比。

问题分析

题目描述

给定一个链表的头节点 head，判断链表是否存在环。如果存在环，返回环的入口节点；如果不存在环，返回 null。例如对于链表 3 -> 2 -> 0 -> 4，其中第四个节点指向第二个节点形成环，则环的入口节点是 2。

问题背景

链表环问题在实际软件工程中并非罕见。考虑一个任务调度系统，其中每个任务可能依赖于另一个任务，如果依赖关系形成循环，系统将陷入死锁。又或者在文件系统中，符号链接可能形成环形引用，遍历时需要检测并避免无限循环。这些场景都体现了链表环问题的重要性。

核心挑战

这个问题的挑战在于如何在不使用额外数据结构（如哈希表或集合）的情况下，仅通过节点的遍历来检测和定位环。哈希表方法虽然直观（将遍历过的节点存入集合，如果遇到已存在的节点则说明有环），但需要 O(n) 的额外空间。而 Floyd 双指针算法只需要 O(1) 的空间，体现了更优雅的算法设计。

Floyd 双指针算法

算法概述

Floyd 判圈算法（Floyd's Cycle Detection Algorithm），又称龟兔赛跑算法，是一种用于检测链表环的高效算法。算法的核心是使用两个不同速度的指针：慢指针（slow）每次移动一步，快指针（fast）每次移动两步。如果链表中存在环，快指针最终会追上慢指针；如果不存在环，快指针会首先到达链表末尾。

这个算法的巧妙之处在于，它不仅能检测环的存在，还能进一步定位环的入口。通过数学推导，我们可以证明：当快慢指针在环中某处相遇后，如果将其中一个指针重置到链表头部，然后两个指针都以每次一步的速度前进，它们再次相遇的位置就是环的入口节点。

数学证明

让我们深入理解为什么这个算法有效。假设链表从头到环入口的距离为 a，从环入口到快慢指针相遇点的距离为 b，环的剩余部分长度为 c（即 c = 环总长度 - b）。那么环的总长度 L = b + c。

慢指针在相遇时走过的距离为 a + b。快指针走过的距离是慢指针的两倍，即 2(a + b)。同时，快指针走过的距离也可以表示为 a + b + kL，其中 k 是快指针在环中多走的完整圈数（因为快指针进入环后可能绕了多圈才与慢指针相遇）。

因此我们有：
2(a + b) = a + b + kL
=> a + b = kL
=> a = kL - b = (k-1)L + (L - b) = (k-1)L + c

这意味着从头节点到环入口的距离 a，等于从相遇点继续绕环 (k-1) 圈后再走 c 的距离。如果我们把一个指针从头节点出发，另一个指针从相遇点出发，两个指针都以每次一步的速度前进，那么它们会在环入口相遇。

代码实现

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def detectCycle(head): if not head or not head.next: return None slow = fast = head has_cycle = False while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: has_cycle = True break if not has_cycle: return None slow = head while slow != fast: slow = slow.next fast = fast.next return slow

这段代码展示了 Floyd 双指针算法的完整实现。第一阶段检测环的存在：如果快指针能够到达末尾（fast 或 fast.next 为 None），则不存在环。第二阶段定位环入口：当确认存在环后，将 slow 指针重置到头部，然后 slow 和 fast 都以每次一步的速度前进，直到它们相遇为止。

哈希表方法

直观解法

除了 Floyd 双指针算法，还有一种更直观的解法：使用哈希表记录遍历过的节点。在遍历链表时，每次到达一个节点，检查该节点是否已经在哈希表中。如果在，说明到达了环的入口，返回该节点；如果不在，将节点添加到哈希表中并继续遍历。

def detectCycle_hash(head): visited = set() curr = head while curr: if curr in visited: return curr visited.add(curr) curr = curr.next return None

这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)。虽然实现更简单，思路更直接，但需要额外的内存空间来存储访问过的节点。在某些内存受限的场景下，Floyd 算法可能是更好的选择。

空间复杂度对比

Floyd 算法的空间复杂度为 O(1)，而哈希表方法的的空间复杂度为 O(n)。当链表很长但环很短时，两种方法的时间复杂度相同（都是 O(n)），但空间效率的差异就变得显著。在实际应用中，应该根据具体场景选择合适的算法。

扩展问题

环的长度

如果我们需要在检测环的同时计算环的长度，可以在找到相遇点后，继续移动指针直到再次回到该点，统计移动的步数即为环的长度。这个操作的时间复杂度为 O(L)，其中 L 是环的长度。

def cycleLength(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break if not fast or not fast.next: return 0 count = 1 curr = slow.next while curr != slow: count += 1 curr = curr.next return count

环的节点数

如果需要统计环中节点的个数，除了上面计算长度的方法外，还可以在定位到环入口后，遍历环一周并计数。但这种方法需要额外标记已访问的节点或知道环的结束条件。

起点到环入口的距离

Floyd 算法的数学证明中，我们已经知道从头到环入口的距离为 a。这个距离可以通过哈希表方法轻松获得：在哈希表中，第一个重复访问的节点就是环入口，该节点的距离就是 a。但在 Floyd 算法中，这个距离是隐式确定的，没有直接输出。

测试用例

def create_cycle_list(values, pos): if not values: return None nodes = [ListNode(v) for v in values] for i in range(len(nodes) - 1): nodes[i].next = nodes[i + 1] if pos != -1: nodes[-1].next = nodes[pos] return nodes[0] def test_detect_cycle(): head1 = create_cycle_list([3, 2, 0, 4], 1) assert detectCycle(head1).val == 2 head2 = create_cycle_list([1, 2], 0) assert detectCycle(head2).val == 1 head3 = create_cycle_list([1], -1) assert detectCycle(head3) is None head4 = create_cycle_list([], -1) assert detectCycle(head4) is None head5 = create_cycle_list([1, 2, 3, 4, 5, 6], 3) assert detectCycle(head5).val == 4 print("所有测试用例通过！")