Back to solutions

Linked List Cycle

EasyLinked List

Return true if a linked list contains a cycle, using O(1) extra memory.

Open problem
Constraints
  • 0 <= nodes <= 10^4
  • -10^5 <= Node.val <= 10^5

Floyd's tortoise and hare

Time O(n)Space O(1)

Advance a slow pointer one step and a fast pointer two steps. If they ever meet, a cycle exists; if fast reaches the end, the list is acyclic.

struct ListNode { int val; ListNode* next; };

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}