Detecting Linked List Cycles: Floyd's Algorithm

1. The Problem: What is a Cycle and Why is it Dangerous?

A linked list is supposed to terminate with a NULL pointer. A cycle occurs when a node's next pointer refers to a previous node in the list, creating a loop.

If you try to traverse a list with a cycle using a standard loop like while (current != NULL), your program will never terminate. In an embedded system, this can lead to a device hanging, a watchdog timer reset, or worse.

One way to detect a cycle is to store every visited node's address in a hash table and check for duplicates. While this works, it requires O(n) extra space, which is often unacceptable in memory-constrained embedded systems. We need a more efficient solution.

The video below introduces this problem and sets the stage for a clever, space-efficient algorithm.

2. Floyd's Cycle-Finding Algorithm: The Tortoise and the Hare

As the video hinted, the most elegant solution is Floyd's Cycle-Finding Algorithm, also known as the "tortoise and hare" algorithm. It uses two pointers that traverse the list at different speeds:

• A slow pointer (the tortoise) moves one node at a time.
• A fast pointer (the hare) moves two nodes at a time.

The logic is as follows:

1. If the list has no cycle, the fast pointer will reach the end (NULL) before the slow pointer.
2. If the list has a cycle, the fast pointer will eventually enter the loop and start circling. The slow pointer will follow it into the loop. Since the fast pointer is moving faster, it is guaranteed to eventually "lap" the slow pointer, meeting it at the same node.

This next video provides an excellent visual demonstration of the algorithm in action.

3. Implementation in C

Now, let's translate this logic into C code. The implementation is surprisingly concise. The most critical part is handling the loop condition correctly to avoid dereferencing a NULL pointer.

Here is a complete C implementation based on the one you just reviewed.

#include <stdio.h>
#include <stdlib.h>

// Standard node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

/*
 * Detects if a cycle exists in a linked list using Floyd's algorithm.
 * Returns: 1 if a loop is found, 0 otherwise.
 */
int detectLoop(Node* head) {
    // Edge case: an empty list or a single-node list can't have a cycle.
    if (head == NULL || head->next == NULL) {
        return 0;
    }

    Node* slow_p = head;
    Node* fast_p = head;

    // The fast pointer moves two steps, so we must ensure both fast_p
    // and fast_p->next are valid before moving.
    while (fast_p != NULL && fast_p->next != NULL) {
        slow_p = slow_p->next;          // Move slow pointer by one
        fast_p = fast_p->next->next;    // Move fast pointer by two

        // If the pointers meet, a cycle is present.
        if (slow_p == fast_p) {
            printf("Loop detected! Meeting at node with data (for example): %d\n", slow_p->data);
            return 1;
        }
    }

    // If the loop terminates, fast_p has reached the end of the list.
    return 0;
}

// Helper function to create a node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return NULL;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // Create a list: 1 -> 2 -> 3 -> 4 -> 5
    Node* head = createNode(1);
    head->next = createNode(2);
    Node* cycle_start = createNode(3);
    head->next->next = cycle_start;
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // Create a cycle: 5 -> 3
    head->next->next->next->next->next = cycle_start; 

    if (detectLoop(head)) {
        printf("The linked list has a cycle.\n");
    } else {
        printf("The linked list does not have a cycle.\n");
    }
    
    // Remember to free memory in a real application! This is omitted for brevity.
    return 0;
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes. In the worst case (a long list with a small cycle at the end), the slow pointer traverses the list approximately once before meeting the fast pointer.
• Space Complexity: O(1). This is the key advantage. We only use two extra pointers, regardless of the list size. This makes the algorithm perfectly suited for embedded systems.

4. Interview Deep Dive: Finding the Start of the Loop

In an interview, a common follow-up question is: "Great, you've detected a cycle. Now, can you find the node where the cycle begins?"

Fortunately, Floyd's algorithm can be extended to do just this. There's a mathematical property at play:

When the slow and fast pointers meet, the distance from the head of the list to the start of the cycle is equal to the distance from the meeting point to the start of the cycle.

This leads to a simple, two-phase algorithm:

1. Phase 1: Detect the cycle. Run the tortoise and hare algorithm as before. If they meet, a cycle exists.
2. Phase 2: Find the start node. After they meet, leave the fast pointer at the meeting point. Reset the slow pointer back to the head of the list. Now, advance both pointers one step at a time. The node where they meet again is the start of the cycle.

Here's a C function that implements both phases:

/*
 * Detects a cycle and returns the starting node of the cycle.
 * Returns: A pointer to the starting node of the cycle, or NULL if no cycle exists.
 */
Node* detectAndGetCycleStart(Node* head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }

    Node* slow_p = head;
    Node* fast_p = head;
    Node* meeting_point = NULL;

    // Phase 1: Detect the cycle
    while (fast_p != NULL && fast_p->next != NULL) {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
        if (slow_p == fast_p) {
            meeting_point = slow_p;
            break;
        }
    }

    // If no meeting point, there is no cycle
    if (meeting_point == NULL) {
        return NULL;
    }

    // Phase 2: Find the start of the cycle
    slow_p = head; // Reset slow pointer to the head
    while (slow_p != fast_p) {
        slow_p = slow_p->next;
        fast_p = fast_p->next; // Fast pointer is now also moving one step at a time
    }

    // Both pointers now meet at the start of the cycle
    return slow_p;
}

If you were to run this function with the main from our previous example, it would correctly return a pointer to cycle_start (the node with data 3).

Conclusion

You've now mastered a classic, highly efficient algorithm that is a staple of technical interviews. Being able to explain and implement it flawlessly, including the extension to find the cycle's start, demonstrates a strong command of pointers and algorithmic problem-solving.

Key Takeaways:

• Cycles in linked lists are a serious bug that can cause infinite loops.
• Floyd's "tortoise and hare" algorithm detects cycles in O(n) time and with O(1) space complexity.
• The algorithm relies on two pointers moving at different speeds: a slow pointer (1 step) and a fast pointer (2 steps). A collision indicates a cycle.
• By resetting one pointer to the head after collision and moving both at the same speed, you can precisely locate the starting node of the cycle.

Preview of the Next Lesson:

We have covered array-based and pointer-based linear data structures. In our next lesson, we will move to a non-linear structure that is fundamental to real-time and embedded systems: the heap. We will learn how to implement a min-heap-based priority queue suitable for managing timers or events in an embedded system. This is a crucial component in RTOS schedulers and event-driven firmware.