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

Concept Flow - Detect if a Linked List is Circular

Start at head node

↓

Initialize two pointers: slow, fast

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

Yes→List is Circular

No↓

Check if fast or fast.next is None?

Yes→List is NOT Circular

↩Back to Move slow and fast

We use two pointers moving at different speeds to detect if the list loops back on itself.

Execution Sample

DSA Rust

fn is_circular(head: Option<&Box<Node>>) -> bool {
    let mut slow = head;
    let mut fast = head;
    while let (Some(s), Some(f)) = (slow, fast) {
        slow = s.next.as_ref();
        fast = f.next.as_ref().and_then(|n| n.next.as_ref());
        if slow == fast && slow.is_some() {
            return true;
        }
    }
    false
}

This function uses two pointers moving at different speeds to check if the linked list loops back.

Execution Table

Step	Operation	Slow Pointer Node	Fast Pointer Node	Pointer Changes	Visual State
1	Initialize slow and fast at head	Node 1	Node 1	slow = head, fast = head	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move slow by 1 step	Node 2	Node 1	slow = Node 2	1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move fast by 2 steps	Node 2	Node 3	fast = Node 3	1 -> 2 -> 3 -> 4 -> 5 -> null
4	Check slow == fast?	Node 2	Node 3	No	1 -> 2 -> 3 -> 4 -> 5 -> null
5	Move slow by 1 step	Node 3	Node 3	slow = Node 3	1 -> 2 -> 3 -> 4 -> 5 -> null
6	Move fast by 2 steps	Node 3	Node 5	fast = Node 5	1 -> 2 -> 3 -> 4 -> 5 -> null
7	Check slow == fast?	Node 3	Node 5	No	1 -> 2 -> 3 -> 4 -> 5 -> null
8	Move slow by 1 step	Node 4	Node 5	slow = Node 4	1 -> 2 -> 3 -> 4 -> 5 -> null
9	Move fast by 2 steps	Node 4	null	fast = null (end of list)	1 -> 2 -> 3 -> 4 -> 5 -> null
10	Check fast or fast.next is None?	Node 4	null	Yes	1 -> 2 -> 3 -> 4 -> 5 -> null
11	Conclusion	Node 4	null	List is NOT Circular	1 -> 2 -> 3 -> 4 -> 5 -> null

💡 fast pointer reached null, so list is not circular

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	After Step 9	Final
slow	Node 1	Node 2	Node 2	Node 3	Node 3	Node 4	Node 4	Node 4
fast	Node 1	Node 1	Node 3	Node 3	Node 5	Node 5	null	null

Key Moments - 3 Insights

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

Moving fast pointer twice as fast ensures that if there is a loop, fast will eventually catch up to slow. This is shown in steps 2, 3, 5, 6, 8, and 9 in the execution_table.

What happens if the list is empty or has only one node?

If head is None or fast or fast.next becomes None early, the loop ends and returns false, meaning no circular list. This is implied in the exit condition at step 10.

Why do we check slow == fast after moving pointers?

Because if slow and fast point to the same node, it means fast caught slow inside a loop, confirming circularity. This check is at steps 4, 7, and would be true if circular.

Visual Quiz - 3 Questions

Look at the execution_table, what node does the slow pointer point to after step 5?

A Node 3

B Node 2

C Node 4

D Node 1

💡 Hint

Check the 'Slow Pointer Node' column at step 5 in execution_table.

At which step does the fast pointer reach the end of the list (null)?

A Step 7

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Fast Pointer Node' column and find when it becomes null.

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

A They would never meet

B They would meet at some node

C Fast pointer would become null

D Slow pointer would become null

💡 Hint

Refer to the 'Check slow == fast?' operation rows where meeting means circular list.

Concept Snapshot

Detect Circular Linked List using two pointers:
- Initialize slow and fast at head
- Move slow by 1 step, fast by 2 steps
- If slow == fast at any point, list is circular
- If fast or fast.next is None, list is not circular
- Uses Floyd’s Cycle Detection Algorithm

Full Transcript

To detect if a linked list is circular, we use two pointers called slow and fast. Both start at the head node. In each step, slow moves one node forward, and fast moves two nodes forward. If the list has a loop, fast will eventually catch up to slow, meaning both pointers point to the same node. If fast reaches the end of the list (null), it means the list is not circular. This method is called Floyd’s Cycle Detection Algorithm. The execution table shows how slow and fast pointers move step by step, and the variable tracker records their positions after each move. Key moments include why fast moves twice as fast, what happens if the list is empty, and why we check if slow equals fast after moving. The visual quiz tests understanding of pointer positions and loop detection.

Practice

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

easy

A. The linked list has no nodes

B. The linked list contains only one node

C. The linked list nodes are sorted in ascending order

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 = last node points back [OK]

Hint: Circular means last node links back to earlier node [OK]

Common Mistakes:

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

2. Which Rust code snippet correctly defines a singly linked list node struct?

easy

A. struct Node { value: i32, next: Option }

B. struct Node { value: i32, next: Node }

C. struct Node { value: i32, next: &Node }

D. struct Node { value: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires using Option for next to allow nullable and heap allocation.

2. Step 2: Check each option

   struct Node { value: i32, next: Option } uses Option, which is correct. Others either lack Option or use references incorrectly.

3. Final Answer:

   struct Node { value: i32, next: Option } -> Option A

4. Quick Check:

   Use Option for next pointer in Rust [OK]

Hint: Use Option for next pointer in Rust [OK]

Common Mistakes:

• Using raw Node type for next causes infinite size error
• Using references without lifetimes
• Omitting Option for nullable next

3. Given the following Rust code to detect a circular linked list, what will be printed?

fn is_circular(head: &Option) -> bool {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while let (Some(s), Some(f)) = (slow, fast) {
        fast = f.next.as_ref().and_then(|n| n.next.as_ref());
        slow = s.next.as_ref();
        if slow == fast {
            return true;
        }
    }
    false
}

// List: 1 -> 2 -> 3 -> 2 (loop back to node with value 2)
// Calling is_circular returns what?

medium

A. false

B. true

C. Compilation error

D. Infinite loop

Solution

1. Step 1: Understand Floyd's cycle detection

   Two pointers move at different speeds; if they meet, list is circular.

2. Step 2: Analyze given list and code

   List loops back from node 3 to node 2, so slow and fast pointers will meet, returning true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Floyd's algorithm detects loop = true [OK]

Hint: Floyd's cycle detection returns true if pointers meet [OK]

Common Mistakes:

• Confusing pointer movement speeds
• Not checking both pointers for null
• Assuming no loop when pointers meet

4. Identify the bug in this Rust function that tries to detect a circular linked list:

fn has_cycle(head: &Option) -> bool {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while fast.is_some() && fast.unwrap().next.is_some() {
        slow = slow.unwrap().next.as_ref();
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
        if slow == fast {
            return true;
        }
    }
    false
}

medium

A. Function always returns false due to wrong loop condition

B. Pointers move at the same speed, so no cycle detection

C. Using unwrap() without checking can cause panic if null

D. Missing return type causes compilation error

Solution

1. Step 1: Check unwrap usage safety

   Using unwrap() without confirming Some can panic if null is encountered.

2. Step 2: Identify risk in loop

   fast.unwrap().next.as_ref().unwrap() assumes next exists, which may not be true at list end.

3. Final Answer:

   Using unwrap() without checking can cause panic if null -> Option C

4. Quick Check:

   Unsafe unwrap causes panic [OK]

Hint: Avoid unwrap without checking Option first [OK]

Common Mistakes:

• Ignoring unwrap panic risk
• Assuming pointers move same speed
• Not checking loop exit conditions

5. You have a linked list where the last node's next pointer is mistakenly set to itself, creating a single-node loop. How should you modify the Rust cycle detection function to correctly detect this case?

hard

A. Use a hash set to store visited nodes and detect repeats

B. Ignore cases where next points to itself, treat as non-circular

C. Only check if fast pointer reaches null to decide no cycle

D. Check if slow and fast pointers meet even if they start at the same node

Solution

1. Step 1: Understand single-node loop problem

   If a node points to itself, Floyd's algorithm may detect cycle, but edge cases can be tricky.

2. Step 2: Use hash set for robust detection

   Storing visited nodes in a hash set helps detect any repeated node, including self-loop cases.

3. Final Answer:

   Use a hash set to store visited nodes and detect repeats -> Option A

4. Quick Check:

   Hash set detects all cycles including self-loops [OK]

Hint: Use hash set to catch all loops including self-pointing nodes [OK]

Common Mistakes:

• Assuming Floyd's algorithm covers all edge cases
• Ignoring self-loop as cycle
• Not handling single-node circular lists