Loop Detector
EasyLinked List
Problem
A job scheduler follows next pointers from job to job. If some pointer leads back to an earlier job, the scheduler would run forever.
You get the list's values as head and an integer pos. If pos is -1 there is no loop; otherwise the last node's next points to the node at index pos (0-based). Your function must first build that link itself, then decide whether the list has a loop without using pos.
Return true if following next from the head never reaches the end, false otherwise. Use O(1) extra memory for the detection.
Example 1
- Input:
- head = [3, 2, 0, -4], pos = 1
- Output:
- true
The tail -4 links back to the node at index 1, so the walk never ends.
Example 2
- Input:
- head = [1, 2], pos = -1
- Output:
- false
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^5 ≤ node.val ≤ 10^5
- pos is -1 or a valid index into the list.
Hint
Show the first hint
Build the loop first: find the tail and the node at index pos, then link them.
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 describes where the tail points.
- Can I just check pos? No: pos is only for set-up; the exercise is the detection.
- Compare nodes or values? Nodes, by identity: values can repeat.
02Brute force
Walk the list and keep every visited node in a hash set; reaching a node already in the set means a loop.
Cost: O(n) time and O(n) memory for the set.
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.