Given the head of a linked list, determine if the list contains a cycle. A cycle exists if some node in the list can be reached again by continuously following the next pointer. Return true if there is a cycle, and false otherwise. The input parameter pos indicates where the tail connects to (for testing purposes), but it is not passed to your function.
Example
head = [3, 2, 0, -4] where the tail (-4) connects back to node with value 2
Output: true
After reaching -4, the next pointer leads back to 2 instead of null, forming a loop: 2 -> 0 -> -4 -> 2 -> .... Since the list never ends, it has a cycle.
Use Floyd's cycle detection with two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps. If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet. If fast reaches null, there's no cycle.
Why this works
Think of two runners on a circular track: the faster one will always lap the slower one. If the linked list has a cycle, the fast pointer (2 steps) will eventually catch up to the slow pointer (1 step) from behind. If there is no cycle, the fast pointer simply reaches the end.
Step by step
- Start both pointers at head — slow and fast both begin at the same position.
- Move at different speeds — slow advances 1 node, fast advances 2 nodes each iteration.
- Check for meeting — if slow and fast ever point to the same node, a cycle exists.
- Check for end — if fast or fast.next is null, the list has an end, so no cycle.
Time: O(n)
Space: O(1)
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) { // fast hits null if no cycle
slow = slow.next;
fast = fast.next.next; // moves twice as fast to catch up in a cycle
if (slow == fast) { // they met — cycle exists
return true;
}
}
return false;
}
}
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) { // fast hits null if no cycle
slow = slow->next;
fast = fast->next->next; // moves twice as fast to catch up in a cycle
if (slow == fast) { // they met — cycle exists
return true;
}
}
return false;
}
};
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next: # fast hits null if no cycle
slow = slow.next
fast = fast.next.next # moves twice as fast to catch up in a cycle
if slow == fast: # they met — cycle exists
return True
return False