Linked List Cycle
You are given the head of a singly linked list. Return true if the list contains a cycle, meaning that following next pointers from the head eventually brings you back to a node you have already visited. Return false if the walk reaches null.
The tests describe each list as [values, pos]: the list holds values in order, and the last node's next points to the node at index pos, or to null when pos is -1. Your function only receives head; it never sees pos.
Try to solve it with 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: true
The last node (7) links back to the node at index 1 (9), so walking the list goes 4, 9, 2, 7, 9, 2, 7, … forever.
Example 2
Input: head = [[1,2],0] Output: true
The second node links back to the head: a loop of two nodes.
Example 3
Input: head = [[1],-1] Output: false
pos = -1 means the last node's next is null: there is no loop.
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 {boolean}
*/
function hasCycle(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.