C Program to Detect a Cycle in a Linked List

C Program to Detect a Cycle in a Linked List

By /

Detecting a cycle in a linked list is an essential operation to ensure the list is correctly structured. Cycles, where a node points back to a previous node, can cause infinite loops during traversal and may lead to crashes or memory issues. Understanding cycle detection is crucial for building robust and safe linked list applications. Different approaches exist, including Floyd’s Tortoise and Hare algorithm, hashing, and Brent’s algorithm, each with its own trade-offs in efficiency and memory usage.

Understanding the Problem

A cycle occurs when a node’s next pointer points to an earlier node in the list, forming a loop. Traversing such a list without detecting the cycle can result in infinite iteration. Efficient algorithms address this challenge in different ways: Floyd’s algorithm uses two pointers moving at different speeds to detect cycles in O(n) time and O(1) space, hashing keeps track of visited nodes to identify repeats, and Brent’s algorithm improves pointer traversal efficiency while still using constant space. Proper detection ensures safe traversal and prevents runtime errors or memory leaks.

Program 1: Detect a Cycle Using Floyd’s Algorithm

This program demonstrates how to detect a cycle in a linked list using two pointers moving at different speeds. If the fast pointer meets the slow pointer, a cycle exists. This method is efficient and works in O(n) time with O(1) space.

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

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

Node *head = NULL;

void insertAtEnd(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (!head) head = newNode;
    else {
        Node *temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }

}

void createCycle(int pos) {

    if (pos < 1) return;

    Node *temp = head, *cycleNode = NULL;
    int count = 1;

    while (temp->next) {
        if (count == pos) cycleNode = temp;
        temp = temp->next;
        count++;
    }

    temp->next = cycleNode;

}

int detectCycle() {

    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }

    return 0;

}

int main() {

    insertAtEnd(10); 
    insertAtEnd(20); 
    insertAtEnd(30); 
    insertAtEnd(40);

    createCycle(2);

    if (detectCycle()) 
        printf("Cycle detected in the linked list\n");
    else 
        printf("No cycle in the linked list\n");

    return 0;

}

This program uses Floyd’s Tortoise and Hare algorithm to detect cycles efficiently. Two pointers traverse the list at different speeds, and if they meet, a cycle exists. The helper function allows creating a cycle for testing.

Program 2: Detect a Cycle Using Hashing

This program demonstrates how to detect a cycle in a linked list by storing the addresses of visited nodes in a hash table. If a node is revisited, a cycle exists. This method works in O(n) time with O(n) space.

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

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

typedef struct HashNode {
    Node *addr;
    struct HashNode *next;
} HashNode;

#define SIZE 1000
HashNode *hashTable[SIZE] = {NULL};

Node *head = NULL;

int hash(Node *ptr) { 
    return ((unsigned long)ptr) % SIZE; 
}

void insertAtEnd(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (!head) head = newNode;
    else {
        Node *temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }
}

void createCycle(int pos) {

    if (pos < 1) return;

    Node *temp = head, *cycleNode = NULL;
    int count = 1;

    while (temp->next) {
        if (count == pos) cycleNode = temp;
        temp = temp->next;
        count++;
    }

    temp->next = cycleNode;

}

int detectCycle() {

    Node *temp = head;

    while (temp) {

        int h = hash(temp);
        HashNode *curr = hashTable[h];

        while (curr) {
            if (curr->addr == temp) return 1;
            curr = curr->next;
        }

        HashNode *newNode = (HashNode*)malloc(sizeof(HashNode));
        newNode->addr = temp;
        newNode->next = hashTable[h];
        hashTable[h] = newNode;
        temp = temp->next;

    }

    return 0;

}

int main() {

    insertAtEnd(10); 
    insertAtEnd(20); 
    insertAtEnd(30); 
    insertAtEnd(40);

    createCycle(2);

    if (detectCycle()) 
        printf("Cycle detected in the linked list\n");
    else 
        printf("No cycle in the linked list\n");

    return 0;

}

This program detects cycles by keeping track of all visited nodes in a hash table. If a node is revisited, a cycle exists. While simple to implement, it requires extra memory proportional to the list size.

Program 3: Detect a Cycle Using Brent’s Algorithm

This program demonstrates how to detect a cycle in a linked list using Brent’s algorithm, which moves a fast pointer in increasing powers-of-two steps. A cycle is detected if the slow and fast pointers meet. This method works in O(n) time with O(1) space.

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

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

Node *head = NULL;

void insertAtEnd(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (!head) head = newNode;
    else {
        Node *temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }

}

void createCycle(int pos) {

    if (pos < 1) return;

    Node *temp = head, *cycleNode = NULL;
    int count = 1;

    while (temp->next) {
        if (count == pos) cycleNode = temp;
        temp = temp->next;
        count++;
    }

    temp->next = cycleNode;

}

int detectCycle() {

    if (!head) return 0;

    Node *slow = head, *fast = head->next;
    int power = 1, lam = 1;

    while (slow != fast) {

        if (!fast || !fast->next) return 0;

        if (lam == power) { 
            slow = fast; 
            power *= 2; 
            lam = 0; 
        }

        fast = fast->next;
        lam++;

    }

    return 1;

}

int main() {

    insertAtEnd(10); 
    insertAtEnd(20); 
    insertAtEnd(30); 
    insertAtEnd(40);

    createCycle(2);

    if (detectCycle())
        printf("Cycle detected in the linked list\n");
    else 
        printf("No cycle in the linked list\n");

    return 0;

}

Brent’s algorithm is similar to Floyd’s but may reduce the number of pointer moves by increasing the fast pointer step in powers of two. It detects cycles efficiently using constant memory.

FAQs

Q1: What is the time complexity of detecting a cycle?
For all three methods—Floyd’s, hashing, and Brent’s—the time complexity is O(n), since each node is visited at most once by the algorithm.

Q2: What is the space complexity?
Floyd’s and Brent’s algorithms use O(1) space because they rely on a fixed number of pointers. The hashing method uses O(n) space to store visited node addresses.

Q3: Can these methods detect cycles in an empty list?
Yes, all methods handle an empty list safely and return that no cycle exists.

Q4: Can these algorithms locate the start of the cycle?
Yes, after detecting a cycle, additional steps can determine the starting node of the loop, especially with Floyd’s algorithm. The hashing method can also identify the first repeated node.

Q5: Which method should I use?
Floyd’s algorithm is preferred for most cases due to its simplicity and constant space usage. Hashing is easier to implement if memory is not a concern, and Brent’s algorithm can slightly reduce pointer steps in certain scenarios.

Conclusion

Detecting cycles in a linked list is essential to prevent infinite loops and ensure safe list operations. Floyd’s Tortoise and Hare, hashing, and Brent’s algorithm provide reliable ways to identify cycles, each with trade-offs in memory and efficiency. Mastering these techniques strengthens your ability to implement robust and efficient linked list-based programs.

References & Additional Resources

The following books and online resources provide both theoretical foundations and practical examples to help you understand linked list operations, cycle detection, and dynamic memory allocation in C.

  1. Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, critical for linked list operations.
  2. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of linked lists, dynamic memory allocation, and related algorithms.
  3. GeeksforGeeks: Detect Cycle in Linked List – Step-by-step explanation and example code for detecting cycles in linked lists.
  4. GeeksforGeeks: Floyd’s Cycle Finding Algorithm – Explanation of Floyd’s Tortoise and Hare algorithm for cycle detection.
  5. Medium: Floyd’s Cycle Finding Algorithm – Practical implementation guide with examples.
  6. Wikipedia: Cycle Detection – Overview of cycle detection methods in data structures.
  7. Programiz: Singly Linked List Basics – Beginner-friendly guide covering fundamental linked list operations.
  8. Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of malloc(), calloc(), realloc(), and free() functions for memory management.
  9. C Standard Library Documentation – Memory Management – Official reference for memory allocation and deallocation functions in C.

Related Posts

Scroll to Top