C Program to Detect a Loop in a Linked List

Introduction

A loop in a linked list occurs when a node’s next pointer points to a previous node in the list, creating a cycle. Detecting a loop is crucial because it can cause an infinite loop during traversal and lead to program crashes. One common method to detect a loop is Floyd’s Cycle-Finding Algorithm, also known as the "Tortoise and Hare" algorithm. This algorithm uses two pointers, one moving slowly (tortoise) and the other moving quickly (hare). If there is a loop, the fast pointer will eventually meet the slow pointer inside the loop.

Example:

• Input: A linked list with nodes forming a loop.
• Output: The program should detect the loop.

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Detects if a loop exists in the linked list.
• Displays whether a loop was detected.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Detect a Loop in the Linked List: Write a function that uses Floyd’s Cycle-Finding Algorithm to detect a loop.
4. Implement the Function to Create a Loop in the Linked List (for testing): Write a function that creates a loop in the linked list for testing purposes.
5. Create a Main Function: In the main() function, create the linked list, create a loop, detect the loop, and display the result.

C Program to Detect a Loop in a Linked List

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

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to detect a loop in the linked list using Floyd's Cycle-Finding Algorithm
int detectLoop(struct Node* head) {
    struct Node *slow_ptr = head, *fast_ptr = head;

    while (slow_ptr != NULL && fast_ptr != NULL && fast_ptr->next != NULL) {
        slow_ptr = slow_ptr->next;          // Move slow_ptr by one step
        fast_ptr = fast_ptr->next->next;    // Move fast_ptr by two steps

        if (slow_ptr == fast_ptr) {
            return 1;  // Loop detected
        }
    }
    return 0;  // No loop detected
}

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

// Function to create a loop in the linked list for testing
void createLoop(struct Node* head, int position) {
    struct Node* temp = head;
    struct Node* loopNode = NULL;
    int count = 1;

    while (temp->next != NULL) {
        if (count == position) {
            loopNode = temp;
        }
        temp = temp->next;
        count++;
    }

    if (loopNode != NULL) {
        temp->next = loopNode;  // Creating a loop
    }
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);

    // Create a loop in the linked list (loop starting at position 2)
    createLoop(head, 2);

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

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Detect a Loop in the Linked List

• The detectLoop function uses Floyd’s Cycle-Finding Algorithm:
  • It uses two pointers, slow_ptr and fast_ptr. Initially, both pointers point to the head of the list.
  • slow_ptr moves one step at a time, while fast_ptr moves two steps at a time.
  • If there is a loop, slow_ptr and fast_ptr will eventually meet inside the loop.
  • If the pointers meet, the function returns 1, indicating a loop is detected. If fast_ptr reaches the end of the list (NULL), the function returns 0, indicating no loop.

Function to Insert a Node at the End of the Linked List

• The insertAtEnd function inserts nodes at the end of the list. This is used to create the initial linked list.

Function to Create a Loop in the Linked List (for Testing)

• The createLoop function creates a loop in the linked list for testing purposes. It connects the last node of the list to a node at a specified position.

Main Function

• The main function creates a linked list by inserting nodes at the end using the insertAtEnd function.
• A loop is created in the linked list using the createLoop function.
• The detectLoop function is then called to check if the loop exists, and the result is displayed.

Output Example

Example Output:

Loop detected in the linked list.

Example Output (No Loop):

If you comment out the createLoop function call, the output will be:

No loop detected in the linked list.

Conclusion

This C program demonstrates how to detect a loop in a linked list using Floyd’s Cycle-Finding Algorithm. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and loop detection in linked lists, making it a useful example for beginners learning data structures in C programming.