Linked List

A chain of boxes where each box only knows the next one.

The idea

A linked list is a treasure hunt: each clue (node) holds a value and tells you where the next clue is. You cannot jump to clue #5; you have to follow the chain from the start. The last clue points to nil (nothing).

Reversing means flipping every arrow. You need three helpers: prev (the part already reversed), curr (the node you are fixing) and next (saved so you do not lose the rest of the chain when you flip the arrow).

Cycle detection: two runners on a track, one twice as fast. On a loop the fast runner eventually laps the slow one and they meet. On a straight track the fast runner just falls off the end.

Watch it work

Try it

Common mistakes

How fast is it?

Reverse: O(n) time, O(1) space – one pass, three pointers. Cycle detection: O(n) time, O(1) space – compare with the hash-set approach, which needs O(n) space.