Detecting a Loop in a Linked List using C

In this guide, we’ll write a C program to detect if a linked list contains a loop.
A loop in a linked list occurs when a node’s next pointer points back to a previous node,
creating a cycle that can lead to an infinite loop when traversing the list.

Program Structure

The program will consist of the following components:

• Node Structure: Defines the structure of a node in the linked list.
• Create Function: Allocates memory for a new node and initializes its data.
• Loop Detection Function: Implements Floyd’s Cycle-Finding Algorithm (Tortoise and Hare) to detect a loop.
• Main Function: Creates a linked list, introduces a loop for testing, and checks if a loop exists.

Program Code

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

// Define the structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect a loop in a linked list
int detectLoop(struct Node* head) {
    struct Node *slow = head, *fast = head;

    while (slow && fast && fast->next) {
        slow = slow->next;           // Move slow pointer by one step
        fast = fast->next->next;     // Move fast pointer by two steps

        // If slow and fast pointers meet, there's a loop
        if (slow == fast) {
            return 1;
        }
    }
    return 0; // No loop found
}

// Main function to test the loop detection
int main() {
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // Creating a loop for testing: connecting the last node to the second node
    head->next->next->next->next->next = head->next;

    if (detectLoop(head)) {
        printf("Loop detected in the linked list.\n");
    } else {
        printf("No loop detected in the linked list.\n");
    }

    return 0;
}

Explanation

The program starts by defining a Node structure, which contains an integer data field and a pointer to the next node.
The createNode function dynamically allocates memory for a new node, initializes its data, and sets the next pointer to NULL.

The core of the loop detection is implemented in the detectLoop function, which uses Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm:

• The slow pointer moves one step at a time.
• The fast pointer moves two steps at a time.
• If there is no loop, the fast pointer will reach the end of the list (i.e., NULL).
• If there is a loop, the slow and fast pointers will eventually meet inside the loop.

In the main function, we create a simple linked list with five nodes.
For testing purposes, we manually introduce a loop by setting the next pointer of the last node to the second node.
Finally, we call the detectLoop function to check for a loop and print the result.

This method is efficient and works in O(n) time complexity with O(1) space complexity, making it an optimal solution for loop detection in linked lists.