progress

~/problems / Linked lists / Linked lists

Where does the cycle start?

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or play this problem's boss fight .

A linked list may loop: the last node's next can point back to some earlier node instead of None. Write detect_cycle(head) that returns the node where the cycle begins (the first node you visit twice when walking from head), or None if the list ends normally.

The list has up to 100,000 nodes. Don't modify the list. A set of visited nodes is accepted by the tests, but try to do without it (O(1) extra memory). ⭐ Bonus: a speed test with 100,000-node lists earns a star in O(n) time.

6 -> 1 -> 8 -> 2 -> (back to 1)    returns the node with value 1
A list 6, 1, 8, 2 whose last node points back to the node with value 1, forming a loop; that node is where the cycle begins
6 -> 1 -> 8 -> (back to 6)         returns the head node
6 -> 1 -> 8 -> None                returns None
5 -> (back to 5)                   returns that single node

Return the node object itself, not its value or index; values may repeat.

Show hint

Two pointers moving through the list at different speeds must meet inside the cycle if there is one. Then think about the distances: how far is the meeting point from the cycle's entry, compared with how far head is from it?

Topic: Linked lists. Dummy heads, pointer rewiring, fast/slow pointers.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc