#22 · Linked List

Linked List Cycle

Given the head of a linked list, return true if the list contains a cycle: some node can be reached again by continuously following next.

EasyLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Cycle in a singly linked list

A cycle means a node's next points back to an earlier node, so a walk from the head never reaches the end. The tail-shaped path before the cycle and the loop itself together look like the letter "ρ".

Memory layout

Nodes are heap objects linked by pointers; the cycle is just one back-pointer. Nothing in a node says "I am in a cycle", so it has to be detected from behavior.

Operation	Cost
walk forward	never terminates if a cycle exists
detect (Floyd / Brent)	O(n) time, O(1) space

Fast and slow pointers (tortoise and hare)

Two pointers walk at different speeds. Inside a loop the faster one gains a fixed distance per step on the slower one, so they must collide; on a straight list the fast one just reaches the end.

Memory layout

Two node references; no marking and no extra structure.

Operation	Cost
Floyd: nodes visited	≤ about 3 × (path before the cycle + cycle length)
space	O(1)

Why it fits

Relative speed turns an unbounded walk into a bounded one: the gap between hare and tortoise changes by one each round, so once both are in the cycle, they meet within at most one cycle length of rounds.
It needs no memory of visited nodes, so it works on huge or read-only lists where a hash set (O(n)) or marking nodes (mutation) is not acceptable.
If there is no cycle, the fast pointer reaches the end first, which terminates the loop: a single check (fast and fast.next exist) handles both outcomes.

Why alternatives degrade

Hash set of visited nodes:: Correct and simple, but O(n) extra memory and hashing cost, and it needs node identity to be hashable.
Marking visited nodes (flag or sentinel):: O(1) space but destroys or mutates the input and is unsafe if the list is read-only or shared.
Counting steps up to a limit:: Only works if you know a bound on the length; a long list would be mistaken for a cycle.

Four approaches, from naive to production

1 · beginner

Set of visited nodes

time O(n)space O(n)

Walk the list and put every node into a set. If you ever see a node that is already in the set, there is a cycle; if you reach the end, there is none.

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> seen;
    for (ListNode* node = head; node; node = node->next) {
        if (seen.count(node)) {
            return true;
        }
        seen.insert(node);
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode node = head; node != null; node = node.next) {
        if (seen.contains(node)) {
            return true;
        }
        seen.add(node);
    }
    return false;
}

def has_cycle(head):
    seen = set()
    node = head
    while node:
        if node in seen:
            return True
        seen.add(node)
        node = node.next
    return False

function hasCycle(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  for (let node = head; node; node = node.next) {
    if (seen.has(node)) {
      return true;
    }
    seen.add(node);
  }
  return false;
}

Flaws & bottlenecks

O(n) extra memory for the set: wasteful for a yes/no question.
Hashing every node costs more than the pointer chasing it protects.
The set must compare nodes by identity (reference), not by value: values may repeat.

Interviewer cross-questions

Why identity and not value?

Say: Different nodes can hold equal values (1 → 2 → 1 is not a cycle). Only the same node object appearing twice proves a cycle, so the set must be keyed by reference/address.

Can you use O(1) memory?

Say: Yes: Floyd's tortoise and hare. Two pointers moving at different speeds meet if and only if there is a cycle.

What is the worst case?

Say: O(n) time and O(n) space when there is no cycle (every node is inserted once), or when the cycle starts late.

2 · intermediate

Mark nodes with a sentinel

time O(n)space O(1)

Redirect each node to a special sentinel node as soon as it has been visited. Meeting a node that already points at the sentinel proves a cycle.

bool hasCycle(ListNode* head) {
    ListNode* visited = new ListNode(0);
    ListNode* node = head;
    while (node) {
        if (node->next == visited) {
            return true;
        }
        ListNode* next = node->next;
        node->next = visited;
        node = next;
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    ListNode visited = new ListNode(0);
    ListNode node = head;
    while (node != null) {
        if (node.next == visited) {
            return true;
        }
        ListNode next = node.next;
        node.next = visited;
        node = next;
    }
    return false;
}

def has_cycle(head):
    visited = ListNode(0)
    node = head
    while node:
        if node.next is visited:
            return True
        nxt = node.next
        node.next = visited
        node = nxt
    return False

function hasCycle(head: ListNode | null): boolean {
  const visited = new ListNode(0);
  let node = head;
  while (node) {
    if (node.next === visited) {
      return true;
    }
    const next = node.next;
    node.next = visited;
    node = next;
  }
  return false;
}

Flaws & bottlenecks

Destroys the list: every next arrow is overwritten, so the structure cannot be used afterwards.
Unsafe if another thread or caller still uses the list, or if the list is immutable / read-only.
It cannot distinguish a node that really points at the sentinel from one we redirected, so the sentinel must be a fresh object.

Interviewer cross-questions

Is it acceptable to modify the input?

Say: Only if the problem says so. Detection questions normally promise a read-only check, so mutating is a correctness bug in real code. It is an instructive trick (O(1) space) but not a safe one.

Could you restore the list?

Say: Not without remembering the original successors, which costs the O(n) memory we were trying to avoid.

Why save next before overwriting?

Say: node.next = visited discards the only reference to the rest of the list, so it has to be copied first.

3 · advanced

Floyd's tortoise and hare

time O(n)space O(1)

Move slow one node and fast two nodes per round. If fast reaches the end there is no cycle; if slow and fast ever stand on the same node, there is one.

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

Flaws & bottlenecks

Pointer chasing: the hare does two dereferences per round, so about 3× the node visits of the simple walk before meeting.
Does not tell you where the cycle starts, or how long it is (needs a second phase).
The null-checks (fast and fast.next) are easy to get wrong: checking only fast crashes on odd-length lists.

Interviewer cross-questions

Why must they meet inside a cycle?

Say: Once both are in the cycle of length c, the hare gains exactly one node on the tortoise per round, so the gap (mod c) shrinks by one each round and hits zero within c rounds. It cannot jump over the tortoise: the gap changes by exactly 1.

How would you find the node where the cycle starts?

Say: After they meet, reset one pointer to the head and move both one step at a time: they meet again exactly at the cycle entrance (Floyd's second phase).

Why check both fast and fast.next?

Say: fast jumps two nodes, so both the node after it and the one after that must exist. An odd-length list without a cycle ends with fast on the last node (fast.next is none).

4 · expert

Brent's algorithm

time O(n)space O(1)

Only the hare walks. The tortoise stays put and teleports onto the hare each time the hare has taken power steps (1, 2, 4, 8, …). When the hare lands on the tortoise there is a cycle; if it falls off the end there is none.

bool hasCycle(ListNode* head) {
    if (!head) return false;
    ListNode* tortoise = head;
    ListNode* hare = head->next;
    int power = 1;
    int lam = 1;
    while (hare && hare != tortoise) {
        if (power == lam) {
            tortoise = hare;
            power *= 2;
            lam = 0;
        }
        hare = hare->next;
        lam++;
    }
    return hare != nullptr;
}

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode tortoise = head;
    ListNode hare = head.next;
    int power = 1;
    int lam = 1;
    while (hare != null && hare != tortoise) {
        if (power == lam) {
            tortoise = hare;
            power *= 2;
            lam = 0;
        }
        hare = hare.next;
        lam++;
    }
    return hare != null;
}

def has_cycle(head):
    if not head:
        return False
    tortoise = head
    hare = head.next
    power = 1
    lam = 1
    while hare and hare is not tortoise:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = hare.next
        lam += 1
    return hare is not None

function hasCycle(head: ListNode | null): boolean {
  if (!head) return false;
  let tortoise = head;
  let hare = head.next;
  let power = 1;
  let lam = 1;
  while (hare && hare !== tortoise) {
    if (power === lam) {
      tortoise = hare;
      power *= 2;
      lam = 0;
    }
    hare = hare.next;
    lam++;
  }
  return hare !== null;
}

Flaws & bottlenecks

Subtler to explain and verify than Floyd's, which is why it is rarely asked in interviews.
May walk a few extra nodes past the earliest possible meeting point (up to about twice the cycle length) before the teleport window is large enough.
Still needs the extra phases (and care) to find the cycle start or length.

Interviewer cross-questions

Why is this faster than Floyd's?

Say: The hare does one pointer dereference per step instead of two, and the tortoise does none (it is only reassigned occasionally). In practice it needs noticeably fewer memory accesses on typical inputs, which matters when each dereference is a cache miss.

Why does doubling power guarantee detection?

Say: Once the tortoise has teleported into the cycle and power is at least the cycle length, the hare can walk once around the loop and land on it. Doubling makes that happen after O(n) total steps.

What invariant does it maintain?

Say: lam is the number of steps the hare has walked since the tortoise last moved. When lam reaches power, the tortoise jumps to the hare, resets lam and doubles the window.

Synchronized code walkthrough

Showing: Set of visited nodes — shares the player above; click any step to jump.

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> seen;
    for (ListNode* node = head; node; node = node->next) {
        if (seen.count(node)) {
            return true;
        }
        seen.insert(node);
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode node = head; node != null; node = node.next) {
        if (seen.contains(node)) {
            return true;
        }
        seen.add(node);
    }
    return false;
}

def has_cycle(head):
    seen = set()
    node = head
    while node:
        if node in seen:
            return True
        seen.add(node)
        node = node.next
    return False

function hasCycle(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  for (let node = head; node; node = node.next) {
    if (seen.has(node)) {
      return true;
    }
    seen.add(node);
  }
  return false;
}

bool hasCycle(ListNode* head) {
    ListNode* visited = new ListNode(0);
    ListNode* node = head;
    while (node) {
        if (node->next == visited) {
            return true;
        }
        ListNode* next = node->next;
        node->next = visited;
        node = next;
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    ListNode visited = new ListNode(0);
    ListNode node = head;
    while (node != null) {
        if (node.next == visited) {
            return true;
        }
        ListNode next = node.next;
        node.next = visited;
        node = next;
    }
    return false;
}

def has_cycle(head):
    visited = ListNode(0)
    node = head
    while node:
        if node.next is visited:
            return True
        nxt = node.next
        node.next = visited
        node = nxt
    return False

function hasCycle(head: ListNode | null): boolean {
  const visited = new ListNode(0);
  let node = head;
  while (node) {
    if (node.next === visited) {
      return true;
    }
    const next = node.next;
    node.next = visited;
    node = next;
  }
  return false;
}

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

bool hasCycle(ListNode* head) {
    if (!head) return false;
    ListNode* tortoise = head;
    ListNode* hare = head->next;
    int power = 1;
    int lam = 1;
    while (hare && hare != tortoise) {
        if (power == lam) {
            tortoise = hare;
            power *= 2;
            lam = 0;
        }
        hare = hare->next;
        lam++;
    }
    return hare != nullptr;
}

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode tortoise = head;
    ListNode hare = head.next;
    int power = 1;
    int lam = 1;
    while (hare != null && hare != tortoise) {
        if (power == lam) {
            tortoise = hare;
            power *= 2;
            lam = 0;
        }
        hare = hare.next;
        lam++;
    }
    return hare != null;
}

def has_cycle(head):
    if not head:
        return False
    tortoise = head
    hare = head.next
    power = 1
    lam = 1
    while hare and hare is not tortoise:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = hare.next
        lam += 1
    return hare is not None

function hasCycle(head: ListNode | null): boolean {
  if (!head) return false;
  let tortoise = head;
  let hare = head.next;
  let power = 1;
  let lam = 1;
  while (hare && hare !== tortoise) {
    if (power === lam) {
      tortoise = hare;
      power *= 2;
      lam = 0;
    }
    hare = hare.next;
    lam++;
  }
  return hare !== null;
}