查看“Cycle detection”的源代码

判断环路也可使用一个集合记录所有访问过的节点，当当前节点已在集合中时说明链表有环，但此方法空间复杂度为 O(n)。

== Floyd 判圈法（Floyd's cycle-finding algorithm） ==

判断链表环路的 O(1) 空间方法。

给定两个指针，fast 和 slow。第一次遍历时 fast 每次迭代前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路且一定存在一个时刻 fast 和 slow 相遇。当 slow 和 fast 第一次相遇时，将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

== 相关题目 ==

=== [https://leetcode.com/problems/linked-list-cycle-ii/ LeetCode 142. Linked List Cycle II] ===

Python 解法：
<syntaxhighlight lang=python>
def detectCycle(self, head: ListNode) -> ListNode:
    # Floyd's cycle-finding algorithm, O(1) space
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            break
    else:
        return None
    fast = head
    while fast is not slow:
        fast = fast.next
        slow = slow.next
    return fast
</syntaxhighlight>

== 另见 ==

* [[wikipedia:Cycle detection]]

[[Category:刷题]]
[[Category:链表]]
[[Category:双指针]]