跳转到内容

怎样用 O(1) 额外空间判断链表有环?为什么快慢指针一定会相遇?

让慢指针每次走一步,快指针每次走两步。无环时快指针会到达末尾;有环时,两者进入环后,快指针每轮相对多走一步,最终会追上慢指针。

def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False

假设环长是 C,两者在环中的相对位置每轮改变一格,至多再经过 C 轮就会重合。比较的是同一个节点对象,不能比较节点值:不同节点也可能保存相同数值。两指针最初都在头部,所以应先移动再判断。

时间 O(n),额外空间 O(1)。需要覆盖空链表、单节点无环、单节点指向自己、环从头部开始和环位于中间。用集合记录已访问节点也能判环,但需要 O(n) 额外空间。

资料

LeetCode 141 题面与常量空间要求。代码和推导为本站编写。