Loop Entry Index
MediumLinked List
Problem
A routing table is a linked list where a corrupted pointer may send the tail back into the list, creating a loop.
You get the list's values as head and an integer pos. If pos is -1 the list has no loop; otherwise the last node's next points back to the node at index pos (0-based). Your function must first build that link itself, then find the loop as if you did not know pos.
Return the 0-based index of the node where the loop begins, or -1 if there is no loop. Use O(1) extra memory for the detection.
Example 1
- Input:
- head = [3, 2, 0, -4], pos = 1
- Output:
- 1
The tail -4 points back to the node at index 1 (value 2); walking forward, that is the first node visited twice.
Example 2
- Input:
- head = [1, 2], pos = 0
- Output:
- 0
Example 3
- Input:
- head = [1], pos = -1
- Output:
- -1
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^5 ≤ node.val ≤ 10^5
- pos is -1 or a valid index into the list.
- Values may repeat, so the answer is an index, not a value.
Hint
Show the first hint
First wire the tail to node pos. Then: a set of visited nodes finds the entry, but costs O(n) memory.
Walkthrough
How to approach it
01Clarify before coding
- Why build the loop myself? The test format is an array, which cannot hold a cycle; pos tells you where the tail points.
- May I use pos to answer directly? No: the point is detection, so treat pos only as set-up.
- Return a node or an index? An index, because values can repeat.
02Brute force
Walk the list storing each visited node (by identity) in a set with its index; the first node seen twice is the entry.
Cost: O(n) time and O(n) extra memory for the set; the constraint asks for O(1).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.