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 第二次相遇时，相遇的节点即为环路的开始点。

相关题目

LeetCode 142. Linked List Cycle II

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

另见

• wikipedia:Cycle detection