Linked List Cycle
Detect a cycle in a singly linked list using Floyd's tortoise-and-hare.
3 min read
fast-slow linked-list
Problem#
Given the head of a singly linked list, return true if the list contains a cycle (some node’s next points back into the list).
Examples#
[3,2,0,-4]with last node pointing back to index 1 →true[1, 2]with no cycle →false
Constraints#
- List length in
[0, 10^4].
Hints#
Hint 1
Two pointers, one stepping by 1 and another by 2. If they ever meet, there’s a cycle.
Approach#
Visited set — O(n) time, O(n) space.
Floyd’s two-pointer — O(n) time, O(1) space. Fast goes twice as fast; if it ever catches slow, there’s a cycle.
Solution#
class Solution {public: 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; }};func hasCycle(head *ListNode) bool { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { return true } } return false}from typing import Optional
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: 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;}class Solution { 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; }}function hasCycle(head: ListNode | null): boolean { let slow = head, fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) return true; } return false;}Editorial#
Inside a cycle of length c, the two pointers’ relative speed is 1, so the gap closes by 1 every step — they’re guaranteed to meet within c steps once both are in the cycle. Outside a cycle, fast reaches null first and we exit.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#