Detect if a Linked List is Circular in DSA C - Time & Space Complexity

Time Complexity: Detect if a Linked List is Circular

O(n)

Understanding Time Complexity

We want to know how long it takes to check if a linked list loops back on itself.

How does the time needed grow as the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Detect if linked list is circular using two pointers
int isCircular(struct Node* head) {
    struct Node *slow = head, *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
}
    

This code uses two pointers moving at different speeds to find a loop in the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves pointers through the list.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the number of steps to detect a loop grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "The fast pointer moves twice as fast, so the time is O(n/2), which is much faster than O(n)."

[OK] Correct: We ignore constants in Big-O, so O(n/2) is still O(n). The time still grows linearly with list size.

Interview Connect

Understanding this helps you explain how to detect loops efficiently, a common real-world problem in linked list handling.

Self-Check

"What if we used only one pointer moving one step at a time? How would the time complexity change?"