What is the fastest approach for Linked List Cycle II?

The two-pointer method (Floyd's Tortoise and Hare) efficiently finds the cycle start with O(n) time and O(1) space.

Can we use a hash table to solve Linked List Cycle II?

Yes, storing visited nodes in a hash set allows detecting the cycle start but requires O(n) extra space.

How do we handle lists with no cycle?

Return null immediately after traversing without revisiting any node; two-pointer or hash table methods both handle this.

Does the problem allow modifying the linked list?

No, the list must remain unaltered to maintain pointer integrity for cycle detection.

Why is pointer manipulation important in Linked List Cycle II?

Correct pointer manipulation ensures detection of the cycle start without extra space, preventing infinite loops and null errors.

#142

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null 。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 …

哈希表链表双指针

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 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) 空间解决此题？

lightbulb

解题思路

方法一：快慢指针

我们先利用快慢指针判断链表是否有环，如果有环的话，快慢指针一定会相遇，且相遇的节点一定在环中。

如果没有环，快指针会先到达链表尾部，直接返回 null 即可。

如果有环，我们再定义一个答案指针 $ans$ 指向链表头部，然后让 $ans$ 和慢指针一起向前走，每次走一步，直到 $ans$ 和慢指针相遇，相遇的节点即为环的入口节点。

为什么这样能找到环的入口节点呢？

我们不妨假设链表头节点到环入口的距离为 $x$ ，环入口到相遇节点的距离为 $y$ ，相遇节点到环入口的距离为 $z$ ，那么慢指针走过的距离为 $x + y$ ，快指针走过的距离为 $x + y + k \times (y + z)$ ，其中 $k$ 是快指针在环中绕了 $k$ 圈。

由于快指针速度是慢指针的 $2$ 倍，因此有 $2 \times (x + y) = x + y + k \times (y + z)$ ，可以推出 $x + y = k \times (y + z)$ ，即 $x = (k - 1) \times (y + z) + z$ 。

也即是说，如果我们定义一个答案指针 $ans$ 指向链表头部，然后 $ans$ 和慢指针一起向前走，那么它们一定会在环入口相遇。

时间复杂度 $O(n)$ ，其中 $n$ 是链表中节点的数目。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ans = head
                while ans != slow:
                    ans = ans.next
                    slow = slow.next
                return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) for both hash table and two-pointer approaches, scanning each node at most twice. Space is O(n) for the hash table method and O(1) for two-pointer technique. Pointer resets and step calculations dominate runtime, especially when the cycle starts near the head.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes pointer manipulation and cycle detection pattern immediately.
question_mark
Candidate distinguishes between detecting a cycle and locating its start.
question_mark
Candidate considers edge cases with null or single-node lists and avoids modifying the original list.

warning

常见陷阱

外企场景

error
Misidentifying the meeting point of fast and slow pointers as the cycle start.
error
Failing to handle empty lists or single-node lists, causing null pointer errors.
error
Using extra space unnecessarily when two-pointer solution suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the cycle length instead of the starting node.
arrow_right_alt
Detect multiple cycles in a list with added constraints.
arrow_right_alt
Modify the list to mark visited nodes and detect the cycle, trading safety for space.

help

常见问题

外企场景

继续练习

#141 环形链表 #160 相交链表 #143 重排链表