Linked List Cycle
EasyLinked lists
You get the head of a singly linked list. Return true if following the next pointers from the head ever brings you back to a node you have already passed, and false if the list ends in null.
On this page a list is written as an array of its values, from head to tail, plus pos: the index of the node the tail’s next points back to, or -1 if the tail points to null. pos only describes the input. It is not passed to your function, which gets the head alone.
Examples
Input: head = [6, 2, 9, 4], pos = 1 Output: true
The tail, 4, points back to the node at index 1, the 2.
Input: head = [6, 2, 9, 4], pos = -1 Output: false
The same values, but the tail points to null, so the walk ends.
Constraints
- The list has 0 to 10⁴ nodes.
-10⁵ ≤ node.val ≤ 10⁵posis-1or a valid index in the list.
Stuck?
Hint 1
Values can repeat, so remembering values is not enough. Remember nodes, or find a way that needs no memory at all.
Hint 2
Move one pointer one step at a time and another two steps. If there is a loop, the fast one laps the slow one and they meet; if not, the fast one reaches null.
The idea
Send two pointers down the list, one moving a node at a time and one moving two. Without a loop the fast one reaches the end. With a loop both end up going round it, and the fast one closes the gap by one node each move, so it lands on the slow one instead of jumping past it.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Both pointers start at the head. No set of visited nodes is needed, so the extra space stays constant.
function hasCycle(head) { let slow = head; let fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false;}The trap
Remembering the values seen so far looks like remembering where you have been, and it works while every value is different. But values can repeat. A list with the same value on two nodes and no loop is reported as having one, because the second node looks like a return to the first.
function hasCycle(head) { const seen = new Set(); for (let node = head; node; node = node.next) { if (seen.has(node.val)) return true; // remembers values, not nodes seen.add(node.val); } return false;}