问题描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
To represent a cycle in the given linked list, we use an integer pos
which represents the position (0-indexed) in the linked list where tail connects to. If pos
is -1
, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
1 | Input: head = [3,2,0,-4], pos = 1 |

Example 2:
1 | Input: head = [1,2], pos = 0 |

Example 3:
1 | Input: head = [1], pos = -1 |

Follow-up:
Can you solve it without using extra space?
Related Topics: Linked List
, Two Pointers
原问题: 142. Linked List Cycle II
中文翻译版: 142. 环形链表 II
解决方案
解决方案1
用一个 Set
保存已访问的节点,此时可以遍历整个链表并返回第一个出现重复的节点。时间复杂度为 O(n)
,空间复杂度为 O(n)
参考解题代码
1 | /** |
解决方案2
方案2是 LeetCode 141 解题思路的进一步改进,算法分为两个阶段:
- 阶段1 : 首先使用快指针
fast
和慢指针slow
遍历链表,如果链表有环,两指针最终会相遇到某个节点 - 阶段2 : 初始化额外的两个指针,
ptr1
指向链表的头节点,ptr2
指向相遇节点。然后,我们每次将它们往前移动一步,直到它们相遇,它们相遇的点就是环的入口,返回这个节点
关于阶段2的实现原理,这里提供一个不错的解答说明:LeetCode: 环形链表 II 官方解答
参考解题代码
1 | /** |