Detect if a Linked List is Circular in DSA Python

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
head -> 1 -> 2 -> 3 -> ↑(back to 1)

Dry Run Walkthrough

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

Goal: Detect if the linked list has a cycle (loops back to an earlier node).

Step 1: Initialize two pointers: slow at head (1), fast at head (1)

slow -> 1 -> 2 -> 3 -> 4 -> ...
fast -> 1 -> 2 -> 3 -> 4 -> ...

Why: Start both pointers at the beginning to begin traversal.

Step 2: Move slow by 1 step to 2, fast by 2 steps to 3

slow -> 1 -> [2] -> 3 -> 4 -> ...
fast -> 1 -> 2 -> [3] -> 4 -> ...

Why: Slow moves one node, fast moves two nodes to detect cycle faster.

Step 3: Move slow by 1 step to 3, fast by 2 steps to 2 (due to cycle)

slow -> 1 -> 2 -> [3] -> 4 -> ...
fast -> 1 -> 2 -> 3 -> 4 -> [2] -> ...

Why: Fast pointer loops back because of cycle, slow pointer moves forward.

Step 4: Move slow by 1 step to 4, fast by 2 steps to 4

slow -> 1 -> 2 -> 3 -> [4] -> ...
fast -> 1 -> 2 -> 3 -> 4 -> ...

Why: Both pointers meet at node 4, confirming a cycle.

Result:

Cycle detected because slow and fast pointers met at node 4.

Annotated Code

DSA Python

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

def is_circular(head):
    if head is None:
        return False
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next  # move slow by 1
        fast = fast.next.next  # move fast by 2
        if slow == fast:
            return True  # cycle detected
    return False  # no cycle

# Driver code to create a circular linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
# Creating a cycle here
head.next.next.next.next = head.next  # 4 points back to 2

print(is_circular(head))

slow = head fast = head

Initialize two pointers at the start of the list

while fast and fast.next:

Continue loop while fast pointer can move ahead

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:

Check if pointers meet, indicating a cycle

return True # cycle detected

Return True immediately when cycle is found

return False # no cycle

Return False if no cycle detected after traversal

Output

True

Complexity Analysis

Time: O(n) because each node is visited at most twice by the pointers

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

Edge Cases

Empty list (head is None)

Returns False immediately because no nodes exist

DSA Python

if head is None:
        return False

Single node without cycle

Returns False because next is None

DSA Python

while fast and fast.next:

Single node with cycle (node points to itself)

Returns True because slow and fast meet immediately

DSA Python

if slow == fast:
            return True

When to Use This Pattern

When you need to check if a linked list loops back to an earlier node, use the two-pointer cycle detection pattern because it efficiently detects cycles without extra memory.

Common Mistakes

Mistake: Moving fast pointer by one step instead of two
Fix: Advance fast pointer by two steps to detect cycle faster

Mistake: Not checking if fast or fast.next is None before moving fast
Fix: Add condition 'while fast and fast.next' to avoid 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.