Reorder Linked List in DSA Rust

Mental Model

We rearrange the list so nodes alternate from start and end, meeting in the middle.

Analogy: Imagine lining up people from two ends of a line and then pairing them one by one towards the center.

1 -> 2 -> 3 -> 4 -> 5 -> null
↓                   ↑
start               end

Dry Run Walkthrough

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

Goal: Rearrange to 1 -> 5 -> 2 -> 4 -> 3 -> null

Step 1: Find middle node using slow and fast pointers

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

Why: We need to split the list into two halves at the middle

Step 2: Split list into two: first half 1->2->3, second half 4->5

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating halves helps us reorder by merging from ends

Step 3: Reverse second half to get 5 -> 4 -> null

Second half reversed: 5 -> 4 -> null

Why: Reversing makes it easy to alternate nodes from front and back

Step 4: Merge first half and reversed second half alternately

1 -> 5 -> 2 -> 4 -> 3 -> null

Why: Alternating nodes from each half achieves the reorder

Result:

1 -> 5 -> 2 -> 4 -> 3 -> null

Annotated Code

DSA Rust

use std::option::Option;
use std::boxed::Box;

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

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

fn reorder_list(head: &mut Option<Box<ListNode>>) {
    // Find middle using slow and fast pointers
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = slow.unwrap().next.as_ref();
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
    }

    // Split second half
    let mut second = slow.unwrap().next.take();

    // Reverse second half
    let mut prev = None;
    while let Some(mut node) = second {
        let next = node.next.take();
        node.next = prev;
        prev = Some(node);
        second = next;
    }

    // Merge two halves
    let mut first = head;
    let mut second = prev;

    while second.is_some() {
        let mut first_next = first.as_mut().unwrap().next.take();
        let mut second_next = second.as_mut().unwrap().next.take();

        first.as_mut().unwrap().next = second;
        first = &mut first.as_mut().unwrap().next.as_mut().unwrap().next;

        second = second_next;

        if first_next.is_some() {
            *first = first_next;
        }
    }
}

fn print_list(head: &Option<Box<ListNode>>) {
    let mut curr = head.as_ref();
    while let Some(node) = curr {
        print!("{}", node.val);
        curr = node.next.as_ref();
        if curr.is_some() {
            print!(" -> ");
        }
    }
    println!(" -> null");
}

fn main() {
    // Create list 1->2->3->4->5->null
    let mut head = Some(Box::new(ListNode::new(1)));
    head.as_mut().unwrap().next = Some(Box::new(ListNode::new(2)));
    head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(4)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(5)));

    reorder_list(&mut head);
    print_list(&head);
}

while fast.is_some() && fast.as_ref().unwrap().next.is_some() { slow = slow.unwrap().next.as_ref(); fast = fast.unwrap().next.as_ref().unwrap().next.as_ref(); }

advance slow and fast pointers to find middle node

let mut second = slow.unwrap().next.take();

split list into two halves by cutting after middle

while let Some(mut node) = second { let next = node.next.take(); node.next = prev; prev = Some(node); second = next; }

reverse second half of the list

while second.is_some() { let mut first_next = first.as_mut().unwrap().next.take(); let mut second_next = second.as_mut().unwrap().next.take(); first.as_mut().unwrap().next = second; first = &mut first.as_mut().unwrap().next.as_mut().unwrap().next; second = second_next; if first_next.is_some() { *first = first_next; } }

merge nodes from first and reversed second half alternately

Output

1 -> 5 -> 2 -> 4 -> 3 -> null

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each node is visited a constant number of times

Space: O(1) because we reorder the list in place without extra data structures

vs Alternative: Naive approach might use extra arrays to reorder, costing O(n) extra space; this method is more space efficient

Edge Cases

empty list

function does nothing and list remains empty

DSA Rust

while fast.is_some() && fast.as_ref().unwrap().next.is_some() {

single node list

list remains unchanged as reorder is trivial

DSA Rust

while fast.is_some() && fast.as_ref().unwrap().next.is_some() {

two node list

list remains unchanged as reorder is trivial

DSA Rust

while fast.is_some() && fast.as_ref().unwrap().next.is_some() {

When to Use This Pattern

When you see a problem asking to reorder a linked list by alternating nodes from front and back, reach for the reorder list pattern because it splits, reverses, and merges halves.

Common Mistakes

Mistake: Not properly splitting the list into two halves causing cycles or incorrect merges
Fix: Use take() on the middle node's next pointer to break the list cleanly

Mistake: Forgetting to reverse the second half before merging
Fix: Reverse the second half to ensure correct alternating order

Mistake: Incorrect pointer updates during merge causing lost nodes
Fix: Carefully save next pointers before re-linking and update pointers stepwise

Summary

Rearranges a linked list so nodes alternate from start and end towards the middle.

Use when you need to reorder a list to alternate nodes from front and back without extra space.

Split the list, reverse the second half, then merge nodes alternately to reorder.

Practice

1. What is the main goal of the Reorder Linked List problem?

easy

A. Sort the linked list in ascending order

B. Reverse the entire linked list

C. Rearrange the list so nodes alternate from start and end

D. Remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list problem requires rearranging nodes so the first node is followed by the last node, then the second node, then the second last node, and so on.

2. Step 2: Differentiate from other operations

   This is different from sorting, reversing, or removing duplicates because it mixes nodes from both ends alternatively.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end -> Option C

4. Quick Check:

   Reorder = alternate start and end nodes [OK]

Hint: Remember: reorder mixes front and back nodes alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means full reversal
• Assuming duplicates are removed

2. Which Rust syntax correctly defines a singly linked list node struct for Reorder Linked List?

easy

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

B. struct Node { val: i32, next: &Node }

C. struct Node { val: i32, next: Box<Node> }

D. struct Node { val: i32, next: Option<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

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

2. Step 2: Check each option

   struct Node { val: i32, next: Option } uses Option which is correct. struct Node { val: i32, next: &Node } uses a reference which is invalid for ownership. struct Node { val: i32, next: Box<Node> } misses Option so no null. struct Node { val: i32, next: Option<Node> } uses Option<Node> which is invalid because Node is not sized.

3. Final Answer:

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

4. Quick Check:

   Rust linked list node = Option [OK]

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

Common Mistakes:

• Using references instead of Box for next
• Omitting Option causing compile errors
• Using non-boxed Node causing size errors

3. Given the linked list 1 -> 2 -> 3 -> 4 -> null, what is the reordered list after applying the reorder algorithm?

medium

A. 1 -> 4 -> 2 -> 3 -> null

B. 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 3 -> 2 -> 4 -> null

D. 1 -> 2 -> 3 -> 4 -> null

Solution

1. Step 1: Identify the reorder pattern on the list

   Start with first node (1), then last node (4), then second node (2), then second last node (3).

2. Step 2: Write the reordered list

   The reordered list is 1 -> 4 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 4 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Reorder 1-2-3-4 = 1-4-2-3 [OK]

Hint: Alternate nodes from front and back to reorder [OK]

Common Mistakes:

• Reversing entire list instead of alternating
• Keeping original order unchanged
• Swapping adjacent nodes incorrectly

4. Consider this Rust function snippet for reordering a linked list:

fn reorder_list(head: &mut Option) {
    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();
    }
}

What is the main issue in this code?

medium

A. The loop condition is incorrect and causes infinite loop

B. Using as_ref() causes immutable borrow, preventing mutation later

C. The unwrap calls will panic if list is empty

D. The slow pointer moves too fast skipping nodes

Solution

1. Step 1: Analyze use of as_ref()

   Using as_ref() creates an immutable reference, so slow and fast cannot be used to mutate the list later.

2. Step 2: Understand mutation needs in reorder

   Reordering requires mutable access to split and merge nodes, so immutable borrows block this.

3. Final Answer:

   Using as_ref() causes immutable borrow, preventing mutation later -> Option B

4. Quick Check:

   Immutable borrow blocks mutation in reorder [OK]

Hint: Use mutable references, not as_ref(), to modify list [OK]

Common Mistakes:

• Ignoring borrow rules causing compile errors
• Assuming unwrap always safe without checks
• Misunderstanding pointer movement speed

5. You have a linked list 1 -> 2 -> 3 -> 4 -> 5 -> null. After splitting the list into two halves, reversing the second half, and merging alternately, what is the final reordered list?

hard

A. 1 -> 2 -> 3 -> 4 -> 5 -> null

B. 5 -> 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 3 -> 5 -> 2 -> 4 -> null

D. 1 -> 5 -> 2 -> 4 -> 3 -> null

Solution

1. Step 1: Split the list into two halves

   For 1->2->3->4->5, the middle is at 3, so first half: 1->2->3, second half: 4->5.

2. Step 2: Reverse the second half

   Reverse 4->5 to get 5->4.

3. Step 3: Merge alternately

   Merge nodes from first and reversed second half: 1->5->2->4->3->null.

4. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> null -> Option D

5. Quick Check:

   Split, reverse second half, merge = 1-5-2-4-3 [OK]

Hint: Split, reverse second half, then merge alternately [OK]

Common Mistakes:

• Not reversing second half before merge
• Merging without alternating nodes
• Incorrect middle node calculation