Detect if a Linked List is Circular in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this code detecting a circular linked list?

Consider the following C code that checks if a linked list is circular. What will it print?

DSA C

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

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

int isCircular(Node* head) {
    if (head == NULL) return 0;
    Node* temp = head->next;
    while (temp != NULL && temp != head) {
        temp = temp->next;
    }
    return (temp == head);
}

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

    head->data = 1; head->next = second;
    second->data = 2; second->next = third;
    third->data = 3; third->next = head; // circular link

    if (isCircular(head)) {
        printf("Circular\n");
    } else {
        printf("Not Circular\n");
    }
    return 0;
}

A Circular

B Not Circular

C Segmentation fault

D Infinite loop

💡 Hint

Check if the traversal reaches back to the head node.

The list is circular because the last node points back to the head. The function returns true and prints "Circular".

❓ Predict Output

intermediate

What is the output when the linked list is not circular?

What will the following code print if the linked list is not circular?

DSA C

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

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

int isCircular(Node* head) {
    if (head == NULL) return 0;
    Node* temp = head->next;
    while (temp != NULL && temp != head) {
        temp = temp->next;
    }
    return (temp == head);
}

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

    head->data = 1; head->next = second;
    second->data = 2; second->next = third;
    third->data = 3; third->next = NULL; // not circular

    if (isCircular(head)) {
        printf("Circular\n");
    } else {
        printf("Not Circular\n");
    }
    return 0;
}

A Infinite loop

B Circular

C Segmentation fault

D Not Circular

💡 Hint

Check if the last node points to NULL.

The last node points to NULL, so the list is not circular. The function returns false and prints "Not Circular".

🔧 Debug

advanced

Why does this code cause an infinite loop when checking circularity?

Examine the code below. Why does it cause an infinite loop when the list is circular?

DSA C

int isCircular(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        temp = temp->next;
    }
    return 0;
}

A Because temp is never updated inside the loop

B Because the function does not handle empty lists

C Because the loop does not stop when temp equals head again

D Because the loop condition should check temp->next, not temp

💡 Hint

Think about what happens when the list is circular and temp moves through nodes.

The loop only stops when temp is NULL, but in a circular list temp never becomes NULL. The condition to stop when temp equals head again is missing, causing an infinite loop.

🧠 Conceptual

advanced

Which method is best to detect a circular linked list efficiently?

Which of the following methods is the most efficient to detect if a linked list is circular?

A Traverse the list and check if any node's next pointer points to the head node

B Use two pointers moving at different speeds (slow and fast) to detect a cycle

C Count nodes and compare with a maximum limit to guess circularity

D Store visited nodes in an array and check for repeats

💡 Hint

Think about time and space efficiency.

The two-pointer method (Floyd's cycle detection) detects cycles in O(n) time and O(1) space, making it efficient.

❓ Predict Output

expert

What is the output of this Floyd's cycle detection code on a circular list?

Given the code below implementing Floyd's cycle detection, what will it print for a circular linked list?

DSA C

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

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

int detectCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1;
        }
    }
    return 0;
}

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

    head->data = 1; head->next = second;
    second->data = 2; second->next = third;
    third->data = 3; third->next = head; // circular

    if (detectCycle(head)) {
        printf("Cycle Detected\n");
    } else {
        printf("No Cycle\n");
    }
    return 0;
}

A Cycle Detected

B Segmentation fault

C No Cycle

D Infinite loop

💡 Hint

Floyd's algorithm detects cycles by meeting slow and fast pointers.

The slow and fast pointers meet inside the cycle, so the function returns 1 and prints "Cycle Detected".