Reorder Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Reordering a Linked List

What is the printed state of the linked list after reordering it with the given Rust code?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

fn reorder_list(head: &mut Option<Box<ListNode>>) {
    let mut vals = Vec::new();
    let mut current = head.as_ref();
    while let Some(node) = current {
        vals.push(node.val);
        current = node.next.as_ref();
    }
    let mut i = 0;
    let mut j = vals.len() - 1;
    let mut current_mut = head.as_mut();
    while i <= j {
        if let Some(node) = current_mut {
            node.val = vals[i];
            i += 1;
            if i > j { break; }
            if let Some(next_node) = node.next.as_mut() {
                next_node.val = vals[j];
                j -= 1;
                current_mut = next_node.next.as_mut();
            } else {
                break;
            }
        } else {
            break;
        }
    }
}

fn print_list(head: &Option<Box<ListNode>>) {
    let mut current = head.as_ref();
    let mut result = Vec::new();
    while let Some(node) = current {
        result.push(node.val);
        current = node.next.as_ref();
    }
    println!("{:?}", result);
}

fn main() {
    let mut head = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 3, next: Some(Box::new(ListNode { val: 4, next: None })) })) })) }));
    reorder_list(&mut head);
    print_list(&head);
}

A [1, 3, 2, 4]

B [4, 3, 2, 1]

C [1, 4, 2, 3]

D [1, 2, 3, 4]

💡 Hint

Think about how the reorder_list function rearranges the values from the ends towards the center.

The reorder_list function collects all values, then alternates assigning from the start and end of the list, resulting in the order 1,4,2,3.

🧠 Conceptual

intermediate

Understanding Reorder Linked List Algorithm

Which step is NOT part of the common approach to reorder a linked list as L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...?

A Sort the linked list in ascending order before merging

B Merge the two halves by alternating nodes

C Find the middle of the linked list using slow and fast pointers

D Reverse the second half of the linked list

💡 Hint

Reordering does not require sorting the list.

The reorder algorithm involves finding the middle, reversing the second half, and merging alternately. Sorting is not required.

🔧 Debug

advanced

Identify the Bug in Reorder Linked List Code

What error will this Rust code cause when trying to reorder a linked list?

DSA Rust

fn reorder_list(head: &mut Option<Box<ListNode>>) {
    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();
    }
    // Further code omitted
}

A Runtime panic due to unwrap on None value

B Logical error causing infinite loop

C Compilation error due to borrowing immutable reference multiple times

D No error, code runs correctly

💡 Hint

Check unwrap calls carefully for possible None values.

The unwrap calls on fast and slow pointers can panic if next is None, causing runtime panic.

📝 Syntax

advanced

Correct Syntax to Reverse a Linked List in Rust

Which option correctly reverses a singly linked list in Rust?

DSA Rust

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    // Fill in the blank
}

A

let mut prev = None;
while let Some(node) = head {
    head = node.next;
    node.next = prev;
    prev = Some(node);
}
prev

B

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

C

let mut prev = None;
while let Some(mut node) = head {
    head = node.next;
    node.next = prev;
    prev = Some(node);
}
prev

D

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

💡 Hint

You need to take ownership of node.next to modify it safely.

Option B correctly uses node.next.take() to move ownership and reassign pointers safely.

🚀 Application

expert

Final Order of Nodes After Reordering

Given the linked list 10 → 20 → 30 → 40 → 50 → 60, what is the order of nodes after applying the reorder list algorithm?

A 10 → 50 → 20 → 40 → 30 → 60

B 60 → 50 → 40 → 30 → 20 → 10

C 10 → 20 → 30 → 40 → 50 → 60

D 10 → 60 → 20 → 50 → 30 → 40

💡 Hint

The reorder alternates nodes from the start and end moving inward.

The reordered list alternates first and last nodes: 10,60,20,50,30,40.

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