Reorder Linked List in DSA Rust - Build from Scratch

Reorder Linked List

📖 Scenario: You are working on a program that manages a singly linked list of numbers. Sometimes, you want to reorder the list so that the nodes are arranged in a special pattern: first node, last node, second node, second last node, and so on.This helps in scenarios like alternating tasks or balancing workloads visually.

🎯 Goal: Build a Rust program that creates a singly linked list, then reorders it in the pattern: first node, last node, second node, second last node, etc.Finally, print the reordered list to see the new order.

📋 What You'll Learn

Create a singly linked list with exact nodes: 1 -> 2 -> 3 -> 4 -> 5 -> None

Add a helper variable to find the middle of the list

Implement the reorder logic by splitting, reversing the second half, and merging

Print the reordered linked list in the format: 1 -> 5 -> 2 -> 4 -> 3 -> None

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in scheduling tasks alternately, balancing workloads, or rearranging data for better visualization.

💼 Career

Understanding linked list manipulation is important for software engineers working with low-level data structures, memory management, and performance optimization.

1

Create the initial singly linked list

Create a singly linked list with nodes containing values 1, 2, 3, 4, and 5 in that order. Use a struct called ListNode with fields val: i32 and next: Option>. Create a variable called head that points to the first node.

DSA Rust

// Define ListNode struct and create the linked list with values 1 to 5
// Your code here

Hint

Use Option> for the next pointer. Create nodes from 1 to 5 and link them by setting next.

2

Add a helper variable to find the middle of the list

Inside main, create two mutable variables called slow and fast both set to head.as_ref(). These will help find the middle node of the list by moving through it at different speeds.

DSA Rust

    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    // Your code here

Hint

Use head.as_ref() to get a reference to the first node for both slow and fast.

3

Implement the reorder logic

Implement the reorder logic inside main by doing the following:
1. Use a while loop to move fast two steps and slow one step until fast reaches the end, to find the middle.
2. Split the list into two halves at slow.
3. Reverse the second half.
4. Merge the two halves by alternating nodes from each half.

DSA Rust

fn reverse(mut head: Option>) -> Option> {
    let mut prev = None;
    while let Some(mut node) = head {
        head = node.next.take();
        node.next = prev;
        prev = Some(node);
    prev
    // Find middle
    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();
    // Split list into two halves
    let mut second_half = slow.unwrap().next.clone();
    let mut first_half = head;
    // Cut the first half
    if let Some(mut node) = first_half.as_mut() {
        let mut current = node.as_mut();
        while current.next.is_some() && current.next.as_ref() != slow.unwrap().next.as_ref() {
            current = current.next.as_mut().unwrap();
        }
        current.next = None;
    // Reverse second half
    second_half = reverse(second_half);
    // Merge two halves
    let mut dummy = ListNode::new(0);
    let mut tail = &mut dummy;
    let mut l1 = first_half;
    let mut l2 = second_half;
    while l1.is_some() || l2.is_some() {
        if let Some(mut node1) = l1 {
            l1 = node1.next.take();
            tail.next = Some(node1);
            tail = tail.next.as_mut().unwrap();
        }
        if let Some(mut node2) = l2 {
            l2 = node2.next.take();
            tail.next = Some(node2);
            tail = tail.next.as_mut().unwrap();
        }
    head = dummy.next;

Hint

Use two pointers slow and fast to find the middle. Then split the list, reverse the second half, and merge by alternating nodes.

4

Print the reordered linked list

Write a while loop to print the values of the reordered linked list starting from head. Print each node's value followed by ->. After the last node, print None.

DSA Rust

    // Your code here

Hint

Use a while loop to traverse the list starting from head.as_ref(). Print each node's val followed by ->. After the loop, print None.

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