Completed
标签
相关企业
难度
LeetCode 第 142 题：环形链表 II（Linked List Cycle II）
题目描述
给定一个链表的头节点
head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。示例：
图示：
解题思路
1. 快慢指针法（Floyd 判圈算法）
核心思想：
- 使用两个指针，
slow和fast，slow每次走一步，fast每次走两步。
- 如果链表有环，
slow和fast一定会相遇。
- 相遇后，将
slow重新指向头节点，然后slow和fast同时每次走一步，再次相遇的节点就是环的入口。
步骤：
- 初始化
slow和fast都指向头节点head。
- 移动
slow和fast，直到它们相遇或fast到达链表末尾。
- 如果相遇，将
slow重新指向head，然后slow和fast同时每次走一步，直到再次相遇。
- 返回相遇的节点（环的入口）。
时间复杂度： O(n)
空间复杂度： O(1)
2. 哈希表法
核心思想：
- 遍历链表，将每个节点存入哈希表。
- 如果当前节点已经存在于哈希表中，说明链表有环，且当前节点就是环的入口。
步骤：
- 初始化一个哈希表
visited。
- 遍历链表，将每个节点存入
visited。
- 如果当前节点已经存在于
visited中，返回该节点。
- 如果遍历结束仍未找到环，返回
null。
时间复杂度： O(n)
空间复杂度： O(n)
详细解答
方法 1：快慢指针法
代码实现：
过程图解：
- 初始化：
- 第一次遍历：
slow每次走一步，fast每次走两步。- 如果
slow和fast相遇，说明链表有环。
- 第二次遍历：
- 将
slow重新指向head，然后slow和fast同时每次走一步。 - 再次相遇的节点就是环的入口。
方法 2：哈希表法
代码实现：
过程图解：
- 初始化：
- 遍历链表：
- 将每个节点存入
visited。 - 如果当前节点已经存在于
visited中，说明链表有环，且当前节点就是环的入口。
总结
- 快慢指针法：时间复杂度 O(n)，空间复杂度 O(1)，适合空间要求严格的场景。
- 哈希表法：时间复杂度 O(n)，空间复杂度 O(n)，适合理解简单的场景。
根据题目要求选择合适的解法即可！如果还有疑问，欢迎随时提问！ 😊
