Linked List Cycle

Check whether a linked list contains a cycle.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Linked List Cycle: With a cycle, a pointer moving two links per round gains one cycle position on a pointer moving one link, so they must meet.

Input and goalCheck whether a linked list contains a cycle.

Initialize both pointers at headFor 1->2->3->4 with 4.next = 2, set slow = fast = node 1. The loop guard passes because fast and fast.next both exist.

slowAt1fastAt1guardfast=1 and fast.next=2

Recognize it

Use it for cycle detection in a deterministic next-pointer structure when constant extra space is required and storing every visited node would be unnecessary.

Keep true

After r loop iterations, slow has followed r next links and fast has followed 2r. If no cycle exists fast reaches null; inside a cycle their relative offset changes by one per round.

Reuse it

Different traversal speeds convert a hidden cycle into an inevitable identity collision; guard every fast hop. The technique transfers to repeated-state sequences and cycle-entry algorithms.

Pattern: Slow and fast pointers.

Simple idea: One pointer moves one step and the other moves two. Inside a cycle, the fast pointer must catch the slow pointer. Without a cycle, the fast pointer reaches the end.

def has_cycle(head: ListNode | None) -> bool:
   slow = head
   fast = head

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

Cost: $O(n)$ time and $O(1)$ space.

The platform supplies ListNode with val and next; this snippet assumes that definition.