给出快慢指针(Floyd)解法与原理。
Floyd 快慢指针:慢指针一次走 1 步,快指针一次走 2 步。若有环,二者必在环内相遇;若无环,快指针先到 null。
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: return True
return False
相遇原理:入环后快指针相对慢指针每步追 1,差距逐步缩小必追上。时间 O(n)、空间 O(1)。
进阶:相遇点再从头与慢指针同步走,交点即环入口(数学可证)。
题目与答案就在本页;收藏、批注和错题重练在应用内