Find Middle Element of Linked List in DSA Rust - Execution Trace

Concept Flow - Find Middle Element of Linked List

Start: head points to first node

↓

Initialize two pointers: slow and fast at head

↓

Loop: fast and fast.next not null?

No→Stop

Yes↓

Move slow by 1 node

↓

Move fast by 2 nodes

↓

Repeat loop

↓

slow now points to middle node

↓

Return slow.data as middle element

Use two pointers moving at different speeds to find the middle node in one pass.

Execution Sample

DSA Rust

fn find_middle(head: Option<Box<Node>>) -> Option<i32> {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while let Some(fast_node) = fast {
        match fast_node.next.as_ref() {
            Some(next_node) => {
                slow = slow.and_then(|slow_node| slow_node.next.as_ref());
                fast = next_node.next.as_ref();
            }
            None => { break; }
        }
    }
    slow.map(|node| node.data)
}

Finds the middle element of a singly linked list using slow and fast pointers.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Visual State
1	Initialize slow and fast at head	Node(data: 10)	Node(data: 10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head (slow, fast)
2	Move slow by 1, fast by 2 nodes	Node(data: 20)	Node(data: 30)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
3	Move slow by 1, fast by 2 nodes	Node(data: 30)	Node(data: 50)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
4	Check fast.next is None, stop loop	Node(data: 30)	Node(data: 50)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
5	Return slow.data as middle element	Node(data: 30)	Node(data: 50)	Middle element is 30

💡 fast reached end or fast.next is None, slow points to middle node

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
slow	Node(data: 10)	Node(data: 20)	Node(data: 30)	Node(data: 30)	Node(data: 30)
fast	Node(data: 10)	Node(data: 30)	Node(data: 50)	Node(data: 50)	Node(data: 50)

Key Moments - 3 Insights

Why do we move fast pointer by two nodes but slow pointer by one?

Moving fast pointer twice as fast ensures when fast reaches the end, slow is at the middle (see execution_table steps 2 and 3).

What happens if the list has even number of nodes?

The slow pointer stops at the second of the two middle nodes because the loop stops when fast or fast.next is None (see exit at step 4).

Why do we check fast.next is not None before moving fast?

To avoid accessing None.next which causes error. This check ensures safe traversal (see condition in step 4).

Visual Quiz - 3 Questions

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

A Node with data 40

B Node with data 20

C Node with data 30

D Node with data 50

💡 Hint

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

At which step does the loop stop because fast.next is None?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' column describing the loop stop condition in execution_table.

If the list had only one node, what would slow point to after initialization?

A None

B The single node

C fast pointer node

D Null pointer

💡 Hint

Refer to variable_tracker start values and concept_flow initialization.

Concept Snapshot

Find Middle Element of Linked List:
- Use two pointers: slow moves 1 step, fast moves 2 steps
- Initialize both at head
- Loop until fast or fast.next is None
- slow points to middle node when loop ends
- Works in one pass, O(n) time
- Handles odd and even length lists gracefully

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head node. In each step, slow moves one node forward, while fast moves two nodes forward. We keep doing this until fast reaches the end or fast.next is None. At that point, slow points to the middle node. This method finds the middle in one pass efficiently. For example, in a list with nodes 10 -> 20 -> 30 -> 40 -> 50, slow ends at node 30, which is the middle. This approach works for both odd and even length lists and avoids errors by checking fast.next before moving fast.

Practice

1. What is the main idea behind finding the middle element of a singly linked list using two pointers?

easy

A. Count all nodes first, then access the middle by index

B. Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end

C. Reverse the list and pick the first element

D. Use a stack to store elements and pop half of them

Solution

1. Step 1: Understand two-pointer technique

   The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

2. Step 2: Identify middle when fast pointer reaches the end

   When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

3. Final Answer:

   Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end -> Option B

4. Quick Check:

   Two-pointer technique = Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end [OK]

Hint: Move fast pointer twice as fast as slow pointer [OK]

Common Mistakes:

• Trying to count nodes first wastes time
• Reversing list is unnecessary
• Using extra space like stack is inefficient

2. Which of the following Rust code snippets correctly initializes a singly linked list node with value 5?

easy

A. let node = Node::new(5, None);

B. let node = Node(value: 5, next: None);

C. let node = Node { value: 5, next: None };

D. let node = Node { 5, None };

Solution

1. Step 1: Recall Rust struct initialization syntax

   Rust structs are initialized with field names and values inside curly braces.

2. Step 2: Match correct syntax for Node struct

   Using Node { value: 5, next: None } matches Rust's struct initialization rules.

3. Final Answer:

   let node = Node { value: 5, next: None }; -> Option C

4. Quick Check:

   Rust struct init = let node = Node { value: 5, next: None }; [OK]

Hint: Use field names inside braces to initialize structs [OK]

Common Mistakes:

• Using parentheses instead of braces
• Omitting field names
• Trying to call a constructor that doesn't exist

3. What will be the output of the following Rust code that finds the middle element of a linked list?

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

fn find_middle(head: &Option) -> i32 {
    let mut slow = head;
    let mut fast = head;
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }
    slow.as_ref().unwrap().value
}

fn main() {
    let node3 = Node { value: 3, next: None };
    let node2 = Node { value: 2, next: Some(Box::new(node3)) };
    let node1 = Node { value: 1, next: Some(Box::new(node2)) };
    let head = Some(Box::new(node1));
    println!("{}", find_middle(&head));
}

medium

A. 2

B. Runtime error

C. 3

D. 1

Solution

1. Step 1: Trace slow and fast pointers through the list

   Initially, slow and fast point to node with value 1. After first loop iteration, slow moves to node 2, fast moves to node 3.

2. Step 2: Check loop condition and final slow pointer value

   Fast's next is None after moving, so loop stops. Slow points to node with value 2, which is the middle.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Middle element = 2 [OK]

Hint: Move fast pointer twice, slow pointer once until fast ends [OK]

Common Mistakes:

• Returning fast pointer value instead of slow
• Not checking fast.next before accessing
• Confusing Option and Box unwraps

4. Identify the bug in this Rust function that tries to find the middle element of a linked list:

fn find_middle(head: &Option) -> i32 {
    let mut slow = head;
    let mut fast = head;
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next;
    }
    slow.as_ref().unwrap().value
}

medium

A. fast pointer moves only one step instead of two

B. slow pointer moves two steps instead of one

C. Missing unwrap on slow pointer

D. Loop condition is incorrect

Solution

1. Step 1: Analyze pointer movements inside the loop

   Slow pointer moves one step correctly, but fast pointer moves only one step instead of two.

2. Step 2: Understand impact on finding middle

   Fast pointer must move two steps to reach end faster; moving one step breaks the logic.

3. Final Answer:

   fast pointer moves only one step instead of two -> Option A

4. Quick Check:

   Fast pointer must move two steps [OK]

Hint: Fast pointer must jump two nodes each loop [OK]

Common Mistakes:

• Moving fast pointer only one step
• Not checking fast.next before accessing
• Confusing slow and fast pointer updates

5. Given a singly linked list with an even number of nodes, how can you modify the two-pointer approach in Rust to return the second middle element?

hard

A. Use a counter to count nodes and return node at count/2

B. Move slow pointer two steps and fast pointer one step in the loop

C. Stop the loop when fast.next.next is None and return slow pointer value

D. Change the loop condition to continue while fast and fast.next are not None, moving fast two steps and slow one step

Solution

1. Step 1: Understand default behavior for even nodes

   Default two-pointer returns first middle when list length is even.

2. Step 2: Modify loop to continue while fast and fast.next exist

   By continuing loop while fast and fast.next are Some, slow moves to second middle when fast reaches end.

3. Final Answer:

   Change the loop condition to continue while fast and fast.next are not None, moving fast two steps and slow one step -> Option D

4. Quick Check:

   Loop condition controls which middle is returned [OK]

Hint: Adjust loop condition to get second middle in even list [OK]

Common Mistakes:

• Swapping slow and fast pointer speeds
• Stopping loop too early
• Using counting instead of two-pointer method