Detect if a Linked List is Circular in DSA Python - Execution Trace

Concept Flow - Detect if a Linked List is Circular

Start at head

↓

Set slow and fast pointers to head

↓

Move slow by 1 step, fast by 2 steps

↓

Check if fast or fast.next is None?

Yes→No cycle, return False

No↓

Check if slow == fast?

Yes→Cycle detected, return True

↩Back to move pointers step

Start with two pointers at the head. Move one slowly and the other faster. If they meet, the list is circular. If the fast pointer reaches the end, it's not circular.

Execution Sample

DSA Python

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

def is_circular(head):
    slow = 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 if the linked list loops back on itself.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Check	Visual State
1	Initialize slow and fast to head	Node(1)	Node(1)	N/A	1 -> 2 -> 3 -> 4 -> 5 -> None
2	Move slow by 1, fast by 2	Node(2)	Node(3)	slow != fast	1 -> 2 -> 3 -> 4 -> 5 -> None
3	Move slow by 1, fast by 2	Node(3)	Node(5)	slow != fast	1 -> 2 -> 3 -> 4 -> 5 -> None
4	Check loop condition (fast and fast.next)	Node(3)	Node(5)	fast.next is None → exit loop	1 -> 2 -> 3 -> 4 -> 5 -> None
5	Exit loop	N/A	N/A	No cycle detected, return False	1 -> 2 -> 3 -> 4 -> 5 -> None

💡 fast pointer reached the end of the list (fast.next is None), so the list is not circular

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
slow	Node(1)	Node(2)	Node(3)	Node(3)	N/A
fast	Node(1)	Node(3)	Node(5)	Node(5)	N/A

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one step?

Moving fast pointer twice as fast ensures that if there is a cycle, fast will eventually catch up to slow inside the loop, as shown in steps 2 and 3 of the execution_table.

What happens if the list is not circular?

If the list is not circular, fast or fast.next will become None, causing the loop to exit and return False, as shown in step 4 and 5.

Why do we check slow == fast inside the loop?

Checking slow == fast detects if the two pointers meet inside the cycle, confirming the list is circular, but in this example, they never meet because the list is not circular.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after step 3?

A Node(5)

B Node(3)

C Node(2)

D Node(4)

💡 Hint

Check the 'slow Pointer Node' column at step 3 in the execution_table.

At which step does 'fast or fast.next is None', causing the loop to exit?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'fast Pointer Node' column and the 'Check' column in the execution_table.

If the linked list was circular, what would happen to the slow and fast pointers?

A They would never meet

B Fast pointer would reach None

C They would meet at some node inside the cycle

D Slow pointer would reach None

💡 Hint

Refer to the concept_flow and key_moments about pointer movement and meeting.

Concept Snapshot

Detect if a Linked List is Circular:
- Use two pointers: slow (1 step), fast (2 steps)
- Start both at head
- Move pointers until fast or fast.next is None (no cycle)
- If slow == fast at any point, cycle exists
- Return True if cycle, else False

Full Transcript

To detect if a linked list is circular, we use two pointers starting at the head. The slow pointer moves one step at a time, and the fast pointer moves two steps. If the list has a cycle, the fast pointer will eventually catch up to the slow pointer inside the loop. If the fast pointer reaches the end (None), the list is not circular. This method efficiently detects cycles without extra memory.