Linked List Cycle II
Medium · Linked Lists · Hash Table · Linked List · Two Pointers
Problem
Given the head of a singly linked list, return the node where its cycle begins: the first node you reach a second time if you keep following next. If the list ends, there is no cycle — return None.
Return the node itself, not its index or its value. Values may repeat, and the tests check that you return the very node where the loop closes. Do not modify the list.
In the tests, with_cycle(values, pos) builds the list and links its last node back to the node at index pos (-1 means no cycle). Your function only gets the head; pos is not passed. Results show a node by its value and its index from the head, such as val 2 at index 1.
Follow-up: can you do it with O(1) extra memory?
Examples
Input: 3 -> 2 -> 0 -> -4, with the tail linked back to index 1 Output: val 2 at index 1
After -4 the walk returns to the node holding 2, so the loop begins there.
Input: 1 -> 2, with the tail linked back to index 0 Output: val 1 at index 0
The last node points back to the head: the whole list is the loop.
Constraints
- 0 <= number of nodes <= 10^4
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index (it only describes the test list)
Approaches
- Remember every node — time O(n), space O(n)
Follow-up
Can you solve it using O(1) (constant) memory?
Related problems
Start free on Cariara · Coding problems · System design studio
