Linked List Cycle

A cycle has no end, so a single pointer running indefinitely cannot tell if it is making forward progress or retracing steps. Two runners on a circular track moving at different speeds must eventually occupy the exact same spot, reducing infinite path detection to pointer coincidence.

Full solution

Floyd's fast/slow pointers: O(n) time, O(1) space, and the runners meet at the same node reference iff a cycle exists.

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

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

The theory behind it

Linked List — the ground this problem stands on. All Linked List problems

What Linked List is

A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.

When to reach for it

Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.

How the pattern works

Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.