Problem
Given the head of a linked list, determine if it has a cycle. A cycle exists if some node’s next pointer leads back to a previously visited node.
Example
Input: head = [3,2,0,-4], pos = 1
Output: trueSolution
Floyd’s tortoise and hare. Slow moves 1 step, fast moves 2. If they meet, there’s a cycle.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return Falsefunction hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
In a cycle, fast eventually laps slow because it moves twice as fast. If there’s no cycle, fast hits null first.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?