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.

Practice

1. What does it mean if a linked list is circular?

easy

A. The linked list nodes are sorted in ascending order

B. The linked list has no nodes

C. The linked list has only one node

D. The last node points back to one of the previous nodes, forming a loop

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option D

4. Quick Check:

   Circular linked list means loop exists [OK]

Hint: Circular means last node links back inside list [OK]

Common Mistakes:

• Thinking circular means sorted
• Confusing empty list with circular
• Assuming single node list is always circular

2. Which of the following Python code snippets correctly checks if a linked list is circular?

easy

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

B. def is_circular(head):
current = head
while current:
current = current.next
return True

C. def is_circular(head):
return head.next == None

D. def is_circular(head):
return head == None

Solution

1. Step 1: Understand Floyd's cycle detection

   Using two pointers (slow and fast) moving at different speeds detects loops if they meet.

2. Step 2: Analyze code correctness

   def is_circular(head): if not head: return False slow = head fast = head.next while fast and fast.next: if slow == fast: return True slow = slow.next fast = fast.next.next return False uses slow and fast pointers correctly and returns True if they meet, else False.

3. Final Answer:

   Code using slow and fast pointers to detect loop -> Option A

4. Quick Check:

   Floyd's cycle detection = def is_circular(head): if not head: return False slow = head fast = head.next while fast and fast.next: if slow == fast: return True slow = slow.next fast = fast.next.next return False [OK]

Hint: Use two pointers moving at different speeds [OK]

Common Mistakes:

• Not checking fast pointer's next before accessing
• Assuming reaching None means circular
• Returning True without loop detection

3. What will be the output of the following code snippet?

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

head = Node(1)
second = Node(2)
third = Node(3)
head.next = second
second.next = third
third.next = head  # Creates a circular linked list

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

print(is_circular(head))

medium

A. True

B. False

C. None

D. Runtime Error

Solution

1. Step 1: Understand list structure

   Nodes 1->2->3, and third points back to head, making a loop.

2. Step 2: Trace Floyd's cycle detection

   Slow and fast pointers will eventually meet inside the loop, so function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Loop detected = True [OK]

Hint: Loop means slow and fast pointers meet [OK]

Common Mistakes:

• Ignoring the loop created by third.next = head
• Assuming function returns False by default
• Confusing None return with False

4. Find the error in the following code that tries to detect if a linked list is circular:

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

medium

A. The function should return True outside the loop unconditionally

B. The slow pointer should move two steps instead of one

C. The while loop condition should check if fast and fast.next exist

D. The fast pointer should start at head.next

Solution

1. Step 1: Analyze while loop condition

   Current condition checks fast.next and fast.next.next but does not check if fast itself is None.

2. Step 2: Correct condition to avoid runtime error

   Should check if fast and fast.next exist before accessing fast.next.next to prevent errors.

3. Final Answer:

   The while loop condition should check if fast and fast.next exist -> Option C

4. Quick Check:

   Check fast and fast.next to avoid errors [OK]

Hint: Always check pointer exists before accessing next [OK]

Common Mistakes:

• Not checking if fast is None before fast.next
• Moving slow pointer incorrectly
• Returning True too early

5. You have a linked list where the last node points to the third node, making it circular. How would you modify the detection function to also return the node where the loop starts?

hard

A. Return the node where slow and fast first meet during detection

B. Use Floyd's algorithm: after detecting loop, reset slow to head and move slow and fast one step until they meet; that node is loop start

C. Return the head node always as loop start

D. Use a hash set to store visited nodes and return the first repeated node

Solution

1. Step 1: Detect loop using Floyd's cycle detection

   Use slow and fast pointers to find if loop exists by meeting inside the loop.

2. Step 2: Find loop start node

   Reset slow to head, then move slow and fast one step at a time; the node where they meet is the loop start.

3. Final Answer:

   Use Floyd's algorithm with reset slow pointer to find loop start -> Option B

4. Quick Check:

   Reset slow and move both pointers to find loop start [OK]

Hint: After loop detection, reset slow to head and move both one step [OK]

Common Mistakes:

• Returning meeting point as loop start without reset
• Always returning head as loop start
• Not handling loop detection before finding start