Linked List Cycle II
You are given the head of a singly linked list. If the list has a cycle, return the node where the cycle begins: the first node on the walk from the head that is part of the loop. If there is no cycle, return null.
The tests describe each list as [values, pos]: the last node's next points to the node at index pos, or to null when pos is -1. Your function only receives head. The values in each test list are distinct, and the tests check the value of the node you return.
Don't modify the list, and try to use O(1) extra memory.
Constraints
- The list has between
0and10^4nodes. -10^5 <= Node.val <= 10^5posis-1or a valid index in the list.
Examples
Example 1
Input: head = [[4,9,2,7],1] Output: 9
The tail (7) links back to index 1, so the cycle starts at the node holding 9. Return that node (the tests compare its value).
Example 2
Input: head = [[10,20],0] Output: 10
The second node links back to the head, so the cycle starts at the head.
Example 3
Input: head = [[5],-1] Output: null
No cycle: return null.
JavaScript you'll use: Linked list and tree nodes Map and Set
/**
* Linked list nodes are provided (you don't need to define them):
* class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } }
*/
/**
* @param {ListNode} head
* @return {ListNode | null}
*/
function detectCycle(head) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.