The problem
A linked list may have a loop: its last node points back to an earlier node instead of None. If it does, return the first node of the loop. If it does not, return None.
5 -> 1 -> 8 -> 3 -> 7 -> 2 -> 6 -> 4
^ |
+-------------------+
loop_start(head) # the node holding 3
Return the node itself, not its value: the tests check which node you return by its position. Use O(1) extra space. To make that fair, the nodes in the tests cannot be put in a set or used as dictionary keys: trying raises TypeError: unhashable type.
Limits
- Up to 100,000 nodes.
- Values can repeat, so you cannot find the loop by looking at values.
Builds on LINK-5 Fast and slow pointers.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The figure's list | Not run | |
| 2 | No loop | Not run | |
| 3 | Empty | Not run | |
| 4 | One node, pointing to itself | Not run | |
| 5 | One node, no loop | Not run | |
| 6 | Whole list is the loop | Not run | |
| 7 | Last node points to itself | Not run | |
| 8 | Same values everywhere | Not run | |
| 9 | 100,000 nodes | Not run |