Linked List — Slow/Fast Pointers (Floyd's Cycle Detection)

What does it solve?

Does a linked list have a cycle (a node whose next points back into the list)? The naive fix stores every visited node in a hash set: O(N) time but O(N) space. Floyd's tortoise and hare does it in O(1) extra space.

Key insight: run two pointers from the head. slow advances one node per step, fast advances two. If the list ends (fast hits null), there's no cycle. If there is a cycle, fast laps the loop and closes the gap on slow by one node each step, so they're guaranteed to land on the same node. Meeting = cycle.

The core idea

// tortoise and hare
slow = head, fast = head
while fast && fast.next:
  slow = slow.next
  fast = fast.next.next
  if slow == fast: return true
return false

Complexity

Time complexity

O(N)

Without a cycle, fast reaches the end in N/2 steps. With one, the pointers meet within one full loop traversal. Linear either way.

Space complexity

O(1)

Just two pointers. No hash set, no extra structure that grows with the list. This is the whole point over the naive approach.

Lists & edge cases

Live animation — slow (1 step) and fast (2 steps) chase through the list

slow (tortoise) fast (hare) both meet cycle edge

Linked list

Pointer positions

slow = — fast = — steps = — cycle = —

Step — of —

slow at

—

+1 per step

fast at

—

+2 per step

gap

—

nodes apart

steps

—

taken

Select a list and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	slow idx	slow val	fast idx	fast val	Meet?

C++ implementation

linked_list_cycle.cpp

#include <bits/stdc++.h>
using namespace std;

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

// Floyd's tortoise and hare: detect a cycle in O(1) space.
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;         // one step
        fast = fast->next->next;   // two steps
        if (slow == fast) return true;  // they met -> cycle
    }
    return false;                  // fast hit null -> no cycle
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars