Detect Cycle in Linked List Floyd's Algorithm in DSA C - Build from Scratch

Detect Cycle in Linked List using Floyd's Algorithm

📖 Scenario: Imagine you are working with a train track system represented as a linked list of stations. Sometimes, the track loops back creating a cycle. Your task is to detect if such a cycle exists in the track.

🎯 Goal: Build a linked list and use Floyd's Cycle Detection Algorithm to find out if there is a cycle in the list.

📋 What You'll Learn

Create a linked list with given nodes

Add a pointer to create a cycle at a specified position

Implement Floyd's cycle detection algorithm using two pointers

Print Cycle detected if a cycle exists, otherwise print No cycle

💡 Why This Matters

🌍 Real World

Detecting cycles in linked lists is important in systems like train track management, network routing, and memory management to avoid infinite loops or repeated processing.

💼 Career

Understanding cycle detection is useful for software engineers working with linked data structures, debugging memory leaks, or designing efficient algorithms.

1

Create the linked list nodes

Create a struct called Node with an integer data and a pointer next. Then create 5 nodes with data values 10, 20, 30, 40, and 50 linked in order.

DSA C

// Define struct Node and create 5 linked nodes with data 10, 20, 30, 40, 50
// Your code here

Hint

Remember to link each node's next pointer to the next node.

2

Create a cycle in the linked list

Add code to make the next pointer of the last node point to the third node to create a cycle.

DSA C

#include 
#include 

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));
    Node* fourth = (Node*)malloc(sizeof(Node));
    Node* fifth = (Node*)malloc(sizeof(Node));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = fourth;

    fourth->data = 40;
    fourth->next = fifth;

    fifth->data = 50;
    fifth->next = NULL;

    // Make the last node point to the third node to create a cycle
    // Your code here

    return 0;
}

Hint

Set fifth->next equal to third to create the cycle.

3

Implement Floyd's Cycle Detection Algorithm

Create two pointers slow and fast starting at head. Move slow by one step and fast by two steps in a loop. If they meet, a cycle exists. If fast or fast->next becomes NULL, no cycle exists.

DSA C

#include 
#include 

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));
    Node* fourth = (Node*)malloc(sizeof(Node));
    Node* fifth = (Node*)malloc(sizeof(Node));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = fourth;

    fourth->data = 40;
    fourth->next = fifth;

    fifth->data = 50;
    fifth->next = third; // cycle created here

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

    // Your code here

    return 0;
}

Hint

Use a while loop to move slow by one and fast by two steps. Check if they meet.

4

Print the result of cycle detection

Print Cycle detected if cycle_found is 1, otherwise print No cycle.

DSA C

#include 
#include 

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));
    Node* fourth = (Node*)malloc(sizeof(Node));
    Node* fifth = (Node*)malloc(sizeof(Node));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = fourth;

    fourth->data = 40;
    fourth->next = fifth;

    fifth->data = 50;
    fifth->next = third; // cycle created here

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

    int cycle_found = 0;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            cycle_found = 1;
            break;
        }
    }

    // Print the result
    // Your code here

    return 0;
}

Hint

Use printf to print the message based on cycle_found.