FAANGPrep Sprint

Linked List Cycle

Detect if a linked list has a cycle.

Problem Understanding

Starting from head, report whether a linked list loops back on itself: whether following next pointers ever brings you back to a node you have already visited, instead of eventually reaching null.

Attempt 1: Hash Set (Brute Force)

We can iterate through the list and store each node we visit in a Hash Set. Before visiting a node, we check if it's already in the set. If it is, we found a cycle. If we reach null, there is no cycle.

Drawback: This uses O(N) extra space to store references to all nodes.

Visualizing the Issue

Using O(N) space is acceptable, but can we do better? Can we detect a cycle using only O(1) space without modifying the list structure?

The Intuition: Floyd's Cycle Finding

Imagine two runners on a circular track. One is fast (Hare) and one is slow (Tortoise). If there is a loop, the Fast runner will eventually lap the Slow runner and they will meet explicitly inside the loop. If there is no loop, the Fast runner will just finish the race (reach null) first.

Interactive Walkthrough

POS = 1 · TAIL → #1

START AT HEAD

head slow fast

→

-4

↺ back to #1

Moves

Answer

—

slow and fast both start at head, node 0 (3)

fast is node 0 (3) and fast.next is node 1 (2) — both exist, keep running

Values

pos

Legend & Complexity

slow: moves one node per step

fast: moves two nodes per step

The node where slow and fast meet

↺ back to …: the tail’s next points back into the list

Time

O(n)

Space

O(1)

Watch the Tortoise and Hare race. When the tail’s next points back into the list, the row ends ↺ back to #k; slow moves one node per step, fast moves two, and they meet inside the cycle. Set pos to -1 to watch fast reach NULL instead.

Dry Run Table

Input: 3 -> 2 -> 0 -> -4 (cycle to index 1, value 2)

Step	Slow (Val)	Fast (Val)	Action
Start	3	3	Init
1	2	0	Slow moves 1, Fast moves 2
2	0	2	Slow moves 1, Fast moves 2
3	-4	-4	Meet! Cycle Detected

The Solution Template

Floyd's Cycle Finding Algorithm.

Linked List Cycle Code

1var hasCycle = function(head) {
2    let slow = head;
3    let fast = head;
4    while (fast && fast.next) {
5        slow = slow.next;
6        fast = fast.next.next;
7        if (slow === fast) return true;
8    }
9    return false;
10};

Edge Cases & Common Mistakes

Empty List: head is null (return false).
Single Node: No cycle possible unless it points to itself.
No Cycle: fast reaches null safely.

Summary

Using two pointers moving at different speeds allows us to detect cycles efficiently without using extra memory.

Previous Problem

Min Arrows to Burst Balloons

Next Problem

Remove Nth Node From End