When you're staring at a whiteboard in a technical interview, the "Linked List Cycle" problem is a classic. It's less about your ability to write a while loop and more about whether you know the specific pattern used to solve this efficiently without using extra memory. If you try to track every node you've visited in a separate list, you're wasting space. We want an $O(1)$ space complexity solution.

Setting up a "Rigged" List

To practice this, we can't just use a standard linear list; we need a list that actually loops back on itself. I'll start by defining a simple node and a helper function to create a cycle manually. This way, we can actually test if our detection logic works.

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_node(int data) {
    Node* new_node = malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

In my test case, I'll create four nodes and point the fourth one back to the second one. That's our "trap."

The Tortoise and the Hare

The trick here is Floyd's Cycle-Finding Algorithm. I like to think of it as a race between a tortoise (slow pointer) and a hare (fast pointer). The slow pointer moves one step at a time, while the fast pointer leaps two. If there is no cycle, the hare hits the end of the list (NULL) and the race is over. But if there is a cycle, the hare will eventually lap the tortoise, and they'll land on the exact same node.

Here is my first attempt at the logic:

int has_cycle(Node* head) {
    Node *slow = head;
    Node *fast = head;

    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next->next; 

        if (slow == fast) {
            return 1; // Cycle detected!
        }
    }
    return 0;
}

Fixing the Segfault

I just ran this in my head, and I realized I made a classic C mistake. Look at fast = fast->next->next;. If fast->next happens to be NULL, trying to access ->next on a NULL pointer will trigger a segmentation fault immediately. I can't just check if fast is NULL; I have to make sure the path ahead is clear for the hare's double-jump.

Let's tighten that loop condition. I'll check both fast and fast->next before I even enter the loop body.

int has_cycle(Node* head) {
    if (head == NULL) return 0;

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

    // Ensure fast can move two steps safely
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return 1;
        }
    }
    return 0;
}

Verifying the Loop

Now the logic is sound. If the list is linear, fast hits the end and returns 0. If the list is circular, fast eventually catches up to slow from behind. It's a clean, elegant solution that doesn't require any extra arrays or hash maps to remember where we've been. The memory stays constant regardless of whether the list has ten nodes or ten million.

📋 Practical Task

Exercise: Implementing a Cycle Detector for a Memory Pool

Imagine you are building a simple memory pool where blocks of memory are linked together. Due to a bug in the allocation logic, some blocks are accidentally pointing back to previous blocks, creating infinite loops during cleanup.

Write a C function int detect_pool_corruption(struct Block* head) that implements the "Tortoise and Hare" algorithm to detect if a cycle exists in a linked list of Block structures. You must handle the following edge cases:

• The list is completely empty (head is NULL).
• The list has only one node that points to itself.
• The list is linear and contains no cycles.

Define your struct Block with an int id and a struct Block* next pointer to complete the implementation.