Linked List Cycle

The obvious way to detect a cycle is to remember every node visited and check if you ever revisit one. The constant-space trick is to use two pointers moving at different speeds — if there is a loop, the faster one is guaranteed to lap the slower one from behind.

Hash Set of Visited Nodes

Time O(n)Space O(n)

Walk the list, storing each node’s identity in a set. If you ever encounter a node already in the set, the next pointers have looped back on themselves.

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

class Solution:
    def hasCycle(self, head: ListNode | None) -> bool:
        seen = set()
        node = head
        while node:
            if node in seen:
                return True
            seen.add(node)
            node = node.next
        return False

Correct and simple, but storing a reference to every visited node costs O(n) extra space — for a problem that is really just “did we ever come back to somewhere we have been,” that is more memory than necessary.

Floyd's Cycle Detection (Slow / Fast Pointers)

OptimalTime O(n)Space O(1)

Move a slow pointer one step at a time and a fast pointer two steps at a time. If there is no cycle, fast reaches the end first and the loop terminates. If there is a cycle, fast enters it first and, moving twice as fast as slow, closes the gap between them by exactly one node per iteration — so it is guaranteed to eventually land on the same node as slow.

class Solution:
    def hasCycle(self, 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

Tracing head = [3,2,0,-4] with the tail’s next wired back to node 2 (index 1) — a cycle. Watch fast, moving at double speed, pull ahead into the loop and then lap slow until they land on the same node:

List

3node 0

2node 1

0node 2

-4node 3

tail next loops back to node 1 (2)

slow

3···

0 moved

fast

3···

0 moved

1 / 7

currentresult

Both pointers start at the head, node 3. Each round slow walks 1 node while fast walks 2, so fast gains 1 node of ground every round.

Why it’s correct: if a cycle exists, once fast enters it, the distance between fast and slow (measured along the cycle) shrinks by exactly one node every iteration, since fast gains one extra step per round — so it cannot skip over slow and must eventually meet it exactly. Complexity: fast traverses at most ~2n node visits before either exiting or meeting slow → O(n) time, and only two pointer variables are used → O(1) space — optimal, matching the follow-up requirement.

Hash Set of Visited Nodes

Floyd's Cycle Detection (Slow / Fast Pointers)

More Linked List practice