Detect if a Linked List is Circular in DSA C

Mental Model

We want to check if the list loops back to an earlier node instead of ending.

Analogy: Imagine walking down a path and checking if you ever step on the same stone twice, meaning the path loops.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 2 (circular back to node with value 2)

Goal: Detect if the list has a loop by finding if any node repeats in the path

Step 1: slow pointer moves to node 2, fast pointer moves to node 3

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 2 (loop)

Why: Start moving pointers at different speeds to detect cycle

Step 2: slow pointer moves to node 3, fast pointer moves to node 2 (loop)

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->2] (loop)

Why: Fast pointer moves twice as fast, may catch slow pointer if cycle exists

Step 3: slow pointer moves to node 4, fast pointer moves to node 4

head -> 1 -> 2 -> 3 -> [slow->4] -> [fast->4] (loop)

Why: Pointers meet at same node, confirming cycle

Result:

head -> 1 -> 2 -> 3 -> 4 -> 2 (loop detected) -> true

Annotated Code

DSA C

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

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

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect if linked list is circular
int isCircular(Node* head) {
    if (head == NULL) return 0; // empty list is not circular

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

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // move slow by 1
        fast = fast->next->next; // move fast by 2

        if (slow == fast) {
            return 1; // cycle detected
        }
    }
    return 0; // no cycle
}

// Driver code
int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    // Creating a cycle: last node points back to node with value 2
    head->next->next->next->next = head->next;

    if (isCircular(head)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

if (head == NULL) return 0; // empty list is not circular

handle empty list edge case

slow = slow->next; // move slow by 1

advance slow pointer by one node

fast = fast->next->next; // move fast by 2

advance fast pointer by two nodes

if (slow == fast) { return 1; }

if pointers meet, cycle detected

Output

true

Complexity Analysis

Time: O(n) because we traverse nodes with two pointers at different speeds, meeting quickly if cycle exists

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Naive approach uses extra memory to store visited nodes (O(n) space), this uses constant space and is faster

Edge Cases

empty list

returns false because no nodes exist

DSA C

if (head == NULL) return 0; // empty list is not circular

single node pointing to itself

detects cycle because slow and fast meet immediately

DSA C

if (slow == fast) { return 1; }

list with no cycle

returns false after fast pointer reaches null

DSA C

while (fast != NULL && fast->next != NULL)

When to Use This Pattern

When you need to check if a linked list loops back on itself, use two pointers moving at different speeds to detect cycles efficiently.

Common Mistakes

Mistake: Not checking if fast or fast->next is NULL before moving fast pointer
Fix: Add condition while (fast != NULL && fast->next != NULL) to avoid null pointer errors

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to know if a linked list loops back to an earlier node.

If two pointers moving at different speeds meet, the list is circular.