AlgoScope

Remove Cycle

After slow and fast meet, walk from the head and the meeting point to the entry, then once round the loop to cut the arrow before it.

Linked list algorithms, algorithm, intermediate
Slow 2, fast 3.123456headslowfast
Slow 2, fast 3.123456headslowfast

List Pointer Puzzles: Cut a loop back to the third node

Decision, step 2 of 10

Slow to 2, fast to 3. Not the same node yet.

How list pointer puzzles works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Taught by the same lesson

List Pointer Puzzles covers these too, in the same run.