Linked List Cycle Entry Index
01 · Problem
A singly linked list may contain a cycle: the tail node's next pointer can link back to an earlier node. Because a cycle cannot be written out as a plain array, the list is described by its node values head plus an integer pos, the 0-based index of the node the tail links back to (pos = -1 means there is no cycle).
Your function receives head as an ordinary acyclic list together with pos. First restore the described structure: if pos != -1, connect the tail's next to the node at index pos. Then, without using pos again and using only O(1) extra memory (no hash sets of visited nodes), find the node where the cycle begins and return its 0-based index in the list. Return -1 if the list has no cycle.
Note: The automated tests only compare the returned index, so they cannot detect whether you reused
pos. Treat the "nopos, O(1) memory" rule as the real interview requirement: your interviewer will check that your solution uses Floyd's cycle detection.
02 · Examples
head = [8,6,4,2], pos = 2
2
The tail (value 2) links back to index 2 (value 4), so the cycle begins at index 2.
head = [9,9], pos = 0
0
The tail links back to the head, so the cycle starts at index 0. Note that values may repeat, so the answer must be an index, not a value.
head = [5], pos = -1
-1
There is no cycle.
03 · Constraints
- 01The number of nodes in the list is in the range [1, 104].
- 02-105 <= Node.val <= 105
- 03pos is -1 or a valid index in the list.
- 04Use O(1) extra memory to detect the cycle entry.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.