Linked List Cycle II
MediumP2Coding
Given the head of a linked list that may contain a cycle, return the 0-based index of the node where the cycle begins (the first node of the cycle reached from the head). If the list has no cycle, return -1.
A list node has val and next. The ListNode class is already defined for you. In the examples and tests, a list with a cycle is written as {"list": [...], "pos": k}: the values in order, with the tail's next pointing back to the node at index k. A plain array is a list without a cycle.
Do not modify the list. Aim for O(1) extra space.
Example 1
- Input
- head = {"list":[3,2,0,-4],"pos":1}
- Output
- 1
Example 2
- Input
- head = {"list":[1,2],"pos":0}
- Output
- 0
Example 3
- Input
- head = [1]
- Output
- -1
Constraints
- 0 <= number of nodes <= 10^4
- -10^5 <= Node.val <= 10^5
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.