← Bank
DSA

Detect Cycle in Linked List

DSAMid~12m
linked-liststwo-pointerfloyd-algorithm

Prompt

We chain job records together with next pointers, and a corruption bug occasionally makes one point back into the chain, so a worker that walks the list loops forever. Given the head of such a list, tell me whether it contains a cycle — and do it without blowing up memory.

How this round runs

I've named a memory concern but not pinned down the exact bound or what you can mutate — clarify before coding, and once you can detect a cycle I'll ask you for more than a yes/no.

Model answer

Clarify first: can I mutate nodes (mark them visited), or is the list read-only? Roughly how long can it get — does an O(n) hash set of nodes fit, or is that the memory I'm being told to avoid? Is an empty or single-node list possible?

The intuitive solution is a hash set of visited nodes — O(n) time but O(n) space, which is exactly the memory I was warned about. Floyd's tortoise-and-hare gets it to O(1) space: two pointers, one stepping by 1 and one by 2. In a cycle the fast pointer gains on the slow one by a node each step, so it can't skip past — they're guaranteed to land on the same node. No cycle, and the fast pointer just runs off the end.

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // +1
    fast = fast.next.next;   // +2
    if (slow === fast) return true;
  }
  return false; // fast hit the end -> no cycle
}

The loop guard checks both fast and fast.next before the double hop, so we never dereference null. Identity comparison (slow === fast) is the same node reference, not equal values.

Dry-run on A -> B -> C -> B...: slow A, fast A; slow B, fast C; slow C, fast C → meet, cycle found.

Signals — what a strong answer shows
  • Asked about the memory bound and whether the list is mutable
  • Named the hash-set approach and its O(n) space cost first
  • Explained why fast and slow must meet inside a cycle, not hand-waved it
  • Guarded both fast and fast.next in the loop and dry-ran a meeting
Follow-ups — where it goes next
  • Return the node where the cycle starts → after they meet, reset one pointer to head and step both by 1; they meet at the entry
  • Return the length of the cycle → once they meet, keep one fixed and walk the other until it comes back, counting steps
Study this: Algorithms