Problems
LinkedList Cycle
Easy·Tagslinked-listtwo-pointers
Problem Statement
Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.
A cycle occurs when a node's `next` pointer points back to a previous node in the list, creating an infinite loop.
Examples
Example 1
Input
head: [3, 2, 0, -4], pos: 1Linked list
Output
"true"Why
The last node links back to the node at index 1 (value 2) instead of ending, so following the pointers loops forever. The list has a cycle.
Example 2
Input
head: [1, 2], pos: 0Linked list
Output
"true"Why
The tail points back to the head node, so traversal never reaches an end. The list has a cycle.
Example 3
Input
head: [1], pos: -1Linked list
Output
"false"Why
The tail points to nothing, so the list simply ends and there is no cycle.
Constraints
- •0 <= Number of Nodes <= 10000
- •-100000 <= Node.val <= 100000
- •pos is -1 or a valid index in the linked-list.
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
Imagine two people running on a track. If the track is a straight line, the faster runner will reach the end and stop. But what happens if the track is a circle?
Hint 2
Use two pointers, 'slow' and 'fast'. Move the 'slow' pointer one node at a time, and the 'fast' pointer two nodes at a time.
Hint 3
If the linked list has a cycle, the 'fast' pointer will eventually lap the 'slow' pointer and they will point to the exact same node.