Linked List Cycle

Signal

"Detect a cycle in O(1) space" is the fast/slow pointer signature — anytime you'd otherwise reach for a seen hash set to detect revisiting a node, ask whether two pointers moving at different speeds can substitute for it.

Approach

Walk two pointers from the head: slow moves one node at a time, fast moves two. If there's no cycle, fast (or fast.next) hits None and you're done. If there is a cycle, fast eventually laps slow from behind and they land on the same node — the closing gap between them shrinks by exactly one node every step, so a meeting is guaranteed once fast enters the loop.

Skeleton

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True
return False

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Complexity

O(n) time — fast traverses at most twice the list length before either exiting or meeting slow. O(1) space — no extra data structure.

Pitfalls

• A seen = set() of visited nodes also works and is easier to write correctly under pressure, but costs O(n) space — name it as the fallback, lead with two-pointer as the intended O(1) answer.
• Comparing with == instead of is "happens" to work here since ListNode doesn't define __eq__, but reach for is deliberately — you're checking identity, not value equality.
• The common follow-up is "return the node where the cycle begins" — that needs a second phase: after slow/fast meet, reset one pointer to head and advance both one step at a time; they meet again exactly at the cycle's start (a consequence of the same distance math).