Detect if a Linked List is Circular in DSA C - Build from Scratch

Detect if a Linked List is Circular

📖 Scenario: Imagine you have a chain of connected train cars. Normally, the last car is not connected to any other car. But sometimes, the last car connects back to one of the earlier cars, making a loop. This is called a circular chain.In programming, a linked list is like this chain of train cars. We want to check if the linked list forms a loop (is circular) or not.

🎯 Goal: You will create a linked list, then write code to check if it is circular (has a loop) or not. Finally, you will print the result.

📋 What You'll Learn

Create a linked list with 4 nodes containing values 10, 20, 30, 40

Add a pointer variable to help detect circularity

Write a function to check if the linked list is circular

Print "Circular" if the list has a loop, otherwise print "Not Circular"

💡 Why This Matters

🌍 Real World

Detecting loops in linked lists is important in software that manages chains of data or tasks, such as operating systems, network packet routing, and memory management.

💼 Career

Understanding how to detect circular linked lists helps in debugging and optimizing programs that use linked data structures, a common task in software development and technical interviews.

1

Create a linked list with 4 nodes

Create a linked list with 4 nodes containing values 10, 20, 30, and 40. Use a struct called Node with an int data and a Node* next. Create a pointer called head that points to the first node.

DSA C

# Define struct Node
// Create 4 nodes with data 10, 20, 30, 40
// Link nodes so that head points to first node
// Your code here

Hint

Remember to create each node with malloc and link them by setting the next pointer.

2

Add a pointer to help detect circularity

Add a pointer variable called slow and set it to head. Also add a pointer called fast and set it to head. These will help us check if the list is circular.

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));

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

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

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

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

    // Add pointers slow and fast to head
    // Your code here

    return 0;
}

Hint

Set both slow and fast pointers to head to start checking from the beginning.

3

Write a function to check if the linked list is circular

Write a function called isCircular that takes a Node* called head and returns 1 if the list is circular, otherwise 0. Use the slow and fast pointer technique: move slow by one step and fast by two steps. If they meet, the list is circular. If fast or fast->next becomes NULL, the list is not circular.

DSA C

#include 
#include 

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

int isCircular(Node* head) {
    // Use slow and fast pointers to detect loop
    // Your code here
}

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));

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

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

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

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

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

    return 0;
}

Hint

Move slow by one step and fast by two steps inside a loop. If they meet, return 1. If fast reaches NULL, return 0.

4

Print if the linked list is circular or not

Call the function isCircular with head. If it returns 1, print "Circular". Otherwise, print "Not Circular".

DSA C

#include 
#include 

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

int isCircular(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return 1; // Circular
        }
    }
    return 0; // Not circular
}

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));

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

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

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

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

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

    // Call isCircular and print result
    // Your code here

    return 0;
}

Hint

Use if (isCircular(head)) to check. Print "Circular" if true, else "Not Circular".