LeetCode 141 — Detect Cycle in Linked List

What does it solve?

Given the head of a linked list, determine whether the list contains a cycle — a node whose next pointer points back to a previously visited node, forming a loop.

Floyd's algorithm uses two pointers: slow advances 1 node per step, fast advances 2. If there's a cycle they must meet inside it. If there's no cycle, fast reaches null first.

The core idea

// Floyd's Tortoise & 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)

At most N steps before fast reaches null or the two pointers collide inside the cycle.

Space complexity

O(1)

Only two pointer variables — no hash set or visited array needed.

Examples & edge cases

Live animation — Floyd's Tortoise & Hare

Slow (tortoise) — 1 step Fast (hare) — 2 steps Both on same node Cycle back-edge Meeting point

slow → node — fast → node — step: —

Step — of —

Slow pointer

—

val: —

Fast pointer

—

val: —

Steps taken

—

iterations

Result

—

Select an example and press Play to start.

🔴 Cycle Detected ✅ No Cycle

Speed Medium

Step-by-step table

Step	Slow (idx)	Slow (val)	Fast (idx)	Fast (val)	Equal?	Action

C++ implementation

detect_cycle.cpp

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// LC 141 — has cycle?
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;           // tortoise: 1 step
        fast = fast->next->next;    // hare: 2 steps
        if (slow == fast) return true;  // met inside cycle
    }
    return false;   // fast reached null — no cycle
}

// LC 142 — find cycle entry node
ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;             // reset slow to head
            while (slow != fast) { slow = slow->next; fast = fast->next; }
            return slow;         // entry of cycle
        }
    }
    return nullptr;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars