Detecting a Cycle in a Linked List (LeetCode 141)

Linked Lists can sometimes hide tricky bugs — one of the most common is a cycle.

A cycle exists if a node’s next pointer eventually points back to a previous node instead of NULL.

In this article, I’ll explain:

1. how I approached the problem
2. why the two-pointer technique works
3. what I learned compared to other approaches

Problem Understanding

You are given the head of a singly linked list.

Your task:

Return true if the linked list contains a cycle, otherwise return false. You cannot modify the list.

Optimal Approach: Fast & Slow Pointers (Floyd’s Cycle Detection)

This problem can be solved efficiently using two pointers:

slow moves 1 step
fast moves 2 steps

Key Insight

If a cycle exists.The fast pointer will eventually catch up to the slow pointer they will point to the same node. If there is no cycle the fast pointer will reach NULL

C++ Implementation

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;           // move 1 step
            fast = fast->next->next;    // move 2 steps

            if (slow == fast)
                return true;             // cycle detected
        }

        return false; // no cycle
    }
};

How It Works (Step-by-Step)

Pointer	Movement
slow	Moves one node at a time
fast	Moves two nodes at a time

If the list has a cycle → pointers meet .If the list doesn’t → fast becomes NULL

Complexity Analysis

Time Complexity O(n)
Space Complexity O(1)

This is the most optimal solution.

Other Approaches I Tried (But Didn’t Use)

1 . Using unordered_map

Store node addresses and count visits.

❌ Extra space
❌ Not optimal

2 . Using unordered_set

Store visited nodes and check repetition.

❌ Extra space
❌ Still O(n) memory

What I Learned

This problem is a pure two-pointer pattern using extra memory is unnecessary .Fast & slow pointer technique is interview-preferred if pointers meet → cycle exists,if fast hits NULL → no cycle

Pattern Takeaway

Whenever you see:

linked list
repetition / cycle

“don’t modify the list” . Think Fast & Slow Pointers

Final Thoughts

This problem helped me understand how pointer speed difference can reveal structure , why optimal solutions often use movement patterns, not extra memory.If you’re learning linked lists, this is a must-master problem.

Happy coding 🚀