Problem
Linked List Cycle
Easy- linked-list
- two-pointers
Tell whether a singly linked list has a cycle. There is one when some node's next leads back to an earlier node in the list, or to the node itself, so walking the list never reaches the end. Return true if there is one, and false if the list ends in null.
Use O(1) extra space: storing the visited nodes in a set is not allowed.
A cycle cannot be written as a plain array, so each example gives the values in order plus pos, the index of the node that the last node points back to. pos = -1 means the last node points to null. pos is only part of the example: your function receives head alone.
- Input
head = [8, 5, 1, 6], pos = 2- Output
true- Explanation
the last node, 6, points back to the node at index 2, which holds 1. Walking the list goes 8, 5, 1, 6, 1, 6 and never stops.
- Input
head = [5], pos = 0- Output
true- Explanation
the only node points back to itself, so the walk never leaves it.
- Input
head = [4, 9, 2], pos = -1- Output
false- Explanation
the last node points to
null, so the list ends.
Constraints:
1 <= number of nodes <= 10^5posis-1or a valid index into the list
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.