Linked List Cycle

Approach Summary

Floyd's tortoise and hare: slow moves 1, fast moves 2. If they meet, there is a cycle.

Full Solution & Approach

Floyd's cycle detection — the tortoise and hare — detects a cycle in O(1) space. Two pointers start at the head: slow advances one node per step, fast advances two. If there is a cycle, fast will eventually lap slow and they will meet inside it; if there is no cycle, fast reaches the end (null) first and you return false. The proof: inside a cycle of length c, each step reduces the distance between the pointers by 1, so they must collide within c steps. The hash-set alternative records every visited node and detects a repeat in O(n) space — simpler but not constant-space. The two-pointer version is the expected interview answer and is the same machinery used to find the middle of a list and to locate the cycle entry point.

The pointers traverse at most the length of the list plus one loop of the cycle — O(n) time. Only two pointer variables — O(1) space.

Solution Code

Solution

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

function 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;
}

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;
}

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;
}

Edge Cases to Watch

Empty list — no cycle
Single node pointing to itself — a cycle
Cycle at the very end of a long list
Two-node cycle — fast catches slow in one lap

How to Recognize This Pattern

Detect cycle in linked list
O(1) space required

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)