Problem
Given the head of a linked list, determine if the linked list contains a cycle. A cycle exists if there is a node in the list that can be reached again by continuously following the next pointer.The pos value is used to indicate the node that the tail connects to and is not provided as an input parameter.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
head = [3,2,0,-4]
pos = 1 Output
trueSolution
This solution uses Floyd's Cycle Detection Algorithm, also known as the Slow and Fast Pointer technique. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.If a cycle exists, the fast pointer will eventually catch up with the slow pointer because both pointers continue moving within the cycle. If there is no cycle, the fast pointer will reach the end of the list.
This approach detects a cycle without using additional data structures such as a HashSet.
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
Complexity
The slow and fast pointers traverse the linked list at different speeds. In the worst case, the pointers may traverse the list or cycle before meeting, resulting in a time complexity ofO(n).
The algorithm uses only two pointers and does not require any additional data structure, resulting in an extra space complexity of
O(1).