题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 1：
- 输入：head = [3,2,0,-4], pos = 1
- 输出：tail connects to node index 1
- 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
- 输入：head = [1,2], pos = 0
- 输出：tail connects to node index 0
- 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
- 输入：head = [1], pos = -1
- 输出：no cycle
- 解释：链表中没有环。
题目思考
- 你是否可以不用额外空间解决此题？
解决方案
思路
- 一个比较容易想到的思路将节点存到集合里面, 然后如果遍历到已经在集合的节点, 就说明存在环, 但这样使用了额外空间, 如何做到不使用额外空间呢?
- 将链表想象成一个跑道, 其中属于环的部分是圆形跑道, 不属于环的部分是直线跑道. 假设有两个人同时从跑道起点出发且速度不同, 什么情况下两人会再次相遇呢?
- 如果跑道没有环, 那么慢的那个人永远追不上快的, 自然不会再次相遇; 但如果有环, 那么总有一个时刻两个人会在环的某个点相遇, 此时快的那个人领先若干圈
- 所以我们可以采用快慢指针的方法, 快指针每次走两步, 慢指针每次走一步, 如果两个指针能相遇, 则说明存在环; 否则如果快指针先到达终点(即空节点), 则说明无环
- 接下来考虑如何求环的起点:
- 找到交点后, 设 head 到环的起点的距离为 x, 环的起点到两个指针交点的距离为 y, 交点继续往后走到环的起点的距离为 z, 慢指针达到交点时走了 m 圈完整的环, 快指针达到交点时走了 n 圈完整的环
- 显然有
2(x+y+m(y+z)) = x+y+n(y+z), 进而得到x=(n-2m-1)(y+z) + z, 也就是说, x 相当于 z 加上若干圈完整的环的距离. - 所以我们可以将指针 a 重新指向链表头, 指针 b 保持在交点不变, 然后两指针每次往前走一步, 那么当 a 走了 x 步到达环路起点时, b 必定走了 z 加若干圈完整的环的距离, 恰好也到了环的起点, 也就是两指针重新出发后第一次相遇的位置, 这样就得到了题目答案
复杂度
- 时间复杂度 O(N): 只需要遍历每个节点常数遍
- 空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 经典快慢指针
# 注意环路起点的求法:
# 找到相等的节点后
# 其中一个指针重新变成head
# 然后和另一个指针每次+1
# 直到再次相交, 该点即为环路起点
# 证明:
# 设head到起点为x, 起点到第一次交点为y, 第一次交点到环起点为z
# 那么2(x+y+m(y+z)) = x+y+n(y+z) (n和m是快慢指针经过环的次数)
# 那么x+y = (n-2m)(y+z) (n-2m>0)
# 那么x = (n-2m-1)(y+z) + z (n-2m-1>=0)
# 即新的头指针经过x步和原来在第一个交点的指针经过x步(可能又走了n-2m-1个环, 加上交点到起点的距离z)所处的位置一定都是环路起点
slow, fast = head, head
while fast:
slow = slow.next
fast = fast.next
if fast:
fast = fast.next
if not fast:
# 没有环
return None
if fast == slow:
break
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号