Skip to content
GKgkml.dev
← Problem set
#141EasyLinked lists

Linked List Cycle

The tell: Detect a loop using constant extra space.

How you get there

  1. 1Move one pointer by one node and another by two.
  2. 2Inside a cycle the fast pointer gains one position per step, so it must eventually meet the slow one.
  3. 3If there is no cycle the fast pointer reaches the end.

Solution

Python
def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
Time
O(n)
Space
O(1)

What goes wrong

Checking `fast.next` before `fast` raises AttributeError on an empty list.

Test yourself on DSANext: Reorder List →