Detect if a Linked List is Circular in DSA Python - 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.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def is_circular(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves two pointers through the list.
• How many times: At most, it runs once per node until pointers meet or list ends.

How Execution Grows With Input

As the list grows, the number of steps grows roughly in a straight line with the number of nodes.

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

Pattern observation: The time grows linearly as the list gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to detect a loop grows in direct proportion to 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 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 input size.

Interview Connect

Understanding this helps you explain how to efficiently find loops in linked lists, a common real-world problem.

Self-Check

"What if we used only one pointer to check for a loop by visiting nodes and marking them? How would the time complexity change?"