When I'm interviewing candidates for C++ roles, the "Linked List Cycle" problem is a classic for a reason. It doesn't just test if you know how pointers work; it tests if you can visualize the movement of data in memory and—more importantly—if you can handle edge cases without crashing the program.

I often see people jump straight into the logic and write something like this. It looks correct at a glance, but it's a landmine:

bool hasCycle(Node* head) {
    Node *slow = head;
    Node *fast = head;

    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next->next; // Potential crash here!
        
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

The Null Pointer Dereference

If you run this code against a list with an even number of nodes that doesn't have a cycle, it will eventually segfault. Why? Look closely at the while condition and the fast pointer movement.

The loop checks if fast is nullptr. But inside the loop, we call fast->next->next. If fast is the very last node in the list, fast->next is nullptr. Trying to access ->next on a nullptr is an immediate crash. I've seen seasoned devs miss this in the heat of a whiteboard session because they're focusing on the algorithm rather than the memory safety.

Securing the Fast Pointer

To fix this, we need to ensure that both the current node and the next node are valid before we try to leapfrog two spaces ahead. Here is how we handle it properly:

bool hasCycle(Node* head) {
    if (!head) return false;

    Node *slow = head;
    Node *fast = head;

    // We must check both fast AND fast->next
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Now, the logic is sound. By checking fast->next != nullptr, we guarantee that the call to fast->next->next is safe. If we hit the end of the list, the loop terminates naturally, and we return false because a list with an end, by definition, cannot have a cycle.

Why the Two-Pointer Approach Actually Works

You might be wondering why we use a "slow" and "fast" pointer (often called Floyd's Cycle-Finding Algorithm) instead of just storing every node we've visited in a std::unordered_set. While a set works, it costs you $O(n)$ extra space. In a production environment or a tight memory constraint, that's a waste.

Think of it like two runners on a track. If the track is a straight line, the fast runner just finishes and leaves. But if the track is a loop, the fast runner will eventually lap the slow runner. In our code, the "lap" happens the moment slow == fast. Because the fast pointer moves exactly one node faster than the slow pointer per iteration, the distance between them shrinks by one node each step until they inevitably collide.

The time complexity remains $O(n)$, but the space complexity drops to $O(1)$. That's the kind of optimization that turns a "pass" into a "strong hire" in a technical interview.

📋 Practical Task

Implement a Cycle-Detection Utility for a Custom Linked List

Write a C++ class LinkedListManager that contains a method bool detectCycle(). You will be provided with a Node structure. Your task is to implement the detection logic using the two-pointer approach discussed in the lesson.

To make it challenging:

• Your implementation must handle empty lists (head == nullptr).
• Your implementation must handle lists with only one node (where that node might or might not point back to itself).
• Ensure there are no memory leaks if you create your own test cases to verify the logic.

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedListManager {
public:
    Node* head;
    LinkedListManager(Node* h) : head(h) {}

    bool detectCycle() {
        // Your implementation here
    }
};