Fast & Slow Pointers (Floyd's Cycle)

Foundations

So far, each pass moved one reference one node at a time. Now, what if you need a position you cannot count to directly, such as the middle of a list whose length is unknown, or whether the list ends at all?

Run two pointers from head: slow takes one step per round and fast takes two. When fast reaches the end, slow has gone half as far, so it sits at the middle. If the last node links back into the list instead of to None, fast never reaches an end; once both are inside the loop, fast gains one node per round and must land on slow. That meeting is Floyd's cycle detection, in O(1) memory.

On 7 → 1 → 5 → 3 → 6, built from nums = [7, 1, 5, 3, 6], both pointers start at 7. After one round slow is at 1 and fast at 5; after two, slow is at 5 and fast at 6, whose .next is None, so the loop stops with slow on the middle. If 6 linked back to 1 instead, fast would wrap around and meet slow at 6 after four rounds.

Case Scenario

Linked List Cycle asks whether following .next from head ever revisits a node. The input head = [3, 2, 0, -4] with pos = 1 means the last node, -4, links back to index 1, the node holding 2. A list that ends would let fast reach None; here fast laps the loop and meets slow, so the answer is True.

The direct approach remembers every node it visits in a set and reports a cycle when one repeats. It finishes in O(n) time, but the set grows with the list, O(n) extra memory, which a long list or a memory-constrained process cannot afford when two pointers would do the same job.