Find Middle Element of Linked List in DSA Rust

Mental Model

To find the middle, move two pointers at different speeds; when the fast one reaches the end, the slow one is in the middle.

Analogy: Imagine two friends walking on a path: one walks twice as fast as the other. When the faster friend reaches the end, the slower friend is exactly halfway.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, find middle element

Goal: Identify the middle node value in the linked list

Step 1: Initialize slow and fast pointers at head (node 1)

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 5 -> null

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow pointer one step to node 2, fast pointer two steps to node 3

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 5 -> null

Why: Slow moves one step, fast moves two steps to find middle efficiently

Step 3: Move slow pointer one step to node 3, fast pointer two steps to node 5

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->5] -> null

Why: Continue moving pointers until fast reaches the end

Step 4: Fast pointer cannot move two steps further, stop; slow pointer is at middle node 3

head -> 1 -> 2 -> [slow->3] -> 4 -> 5 -> null

Why: Fast pointer reached the end, slow pointer is at the middle

Result:

head -> 1 -> 2 -> [3] -> 4 -> 5 -> null
Middle element is 3

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn find_middle(head: Option<Rc<RefCell<ListNode>>>) -> Option<i32> {
    let mut slow = head.clone();
    let mut fast = head.clone();

    while let (Some(f), Some(f_next)) = (fast.clone(), fast.clone().and_then(|f| f.borrow().next.clone())) {
        slow = slow.and_then(|s| s.borrow().next.clone()); // move slow one step
        fast = f_next.borrow().next.clone(); // move fast two steps
    }

    slow.map(|node| node.borrow().val)
}

fn print_list(head: &Option<Rc<RefCell<ListNode>>>) {
    let mut current = head.clone();
    while let Some(node) = current {
        print!("{} -> ", node.borrow().val);
        current = node.borrow().next.clone();
    }
    println!("null");
}

fn main() {
    // Create linked list 1 -> 2 -> 3 -> 4 -> 5 -> null
    let n1 = ListNode::new(1);
    let n2 = ListNode::new(2);
    let n3 = ListNode::new(3);
    let n4 = ListNode::new(4);
    let n5 = ListNode::new(5);

    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());
    n3.borrow_mut().next = Some(n4.clone());
    n4.borrow_mut().next = Some(n5.clone());

    print!("Linked list: ");
    print_list(&Some(n1.clone()));

    let middle = find_middle(Some(n1));
    match middle {
        Some(val) => println!("Middle element is {}", val),
        None => println!("List is empty"),
    }
}

while let (Some(f), Some(f_next)) = (fast.clone(), fast.clone().and_then(|f| f.borrow().next.clone())) {

check if fast pointer can move two steps ahead to continue loop

slow = slow.and_then(|s| s.borrow().next.clone()); // move slow one step

advance slow pointer by one node

fast = f_next.borrow().next.clone(); // move fast two steps

advance fast pointer by two nodes

slow.map(|node| node.borrow().val)

return value at slow pointer which is middle node

Output

Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Middle element is 3

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers moving at different speeds

Space: O(1) because we use only two pointers regardless of list size

vs Alternative: Compared to counting nodes first then accessing middle, this method finds middle in one pass, saving time

Edge Cases

empty list

returns None indicating no middle element

DSA Rust

slow.map(|node| node.borrow().val)

single element list

returns the single element as middle

DSA Rust

while let (Some(f), Some(f_next)) = (fast.clone(), fast.clone().and_then(|f| f.borrow().next.clone()))

even number of elements

returns the second middle element (e.g., for 4 nodes returns node 3)

DSA Rust

while let (Some(f), Some(f_next)) = (fast.clone(), fast.clone().and_then(|f| f.borrow().next.clone()))

When to Use This Pattern

When you need to find the middle of a linked list efficiently, use the slow and fast pointer pattern because it finds the middle in one pass without extra space.

Common Mistakes

Mistake: Moving the fast pointer only one step instead of two, causing incorrect middle detection
Fix: Ensure the fast pointer moves two steps each iteration to maintain the speed difference

Mistake: Not checking if fast pointer or its next is None before moving, causing runtime errors
Fix: Use safe checks like while let to confirm fast and fast.next exist before advancing

Summary

Finds the middle node of a linked list using two pointers moving at different speeds.

Use when you want to find the middle element in a single pass without knowing the list length.

The key insight is that when the fast pointer reaches the end, the slow pointer is at the middle.

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