Reorder Linked List in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a mutable reference to the head of the linked list.

DSA Rust

let mut current = [1];

Drag options to blanks, or click blank then click option'

A&head

B&mut head

Chead

Dmut head

Attempts:

3 left

💡 Hint

Common Mistakes

Using immutable reference '&head' instead of mutable '&mut head'.

Using 'head' directly without reference.

We need a mutable reference to the head to modify the list nodes.

2fill in blank

medium

Complete the code to find the middle node of the linked list using slow and fast pointers.

DSA Rust

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();
}
let mid = [1];

Drag options to blanks, or click blank then click option'

ANone

Bfast

Chead

Dslow

Attempts:

3 left

💡 Hint

Common Mistakes

Using fast pointer as middle node.

Using head instead of slow pointer.

The slow pointer ends at the middle node after the loop.

3fill in blank

hard

Fix the error in reversing the second half of the linked list.

DSA Rust

let mut prev = None;
let mut curr = mid;
while let Some(mut node) = curr {
    let next = node.next.take();
    node.next = [1];
    prev = Some(node);
    curr = next;
}

Drag options to blanks, or click blank then click option'

Acurr

Bnext

Cprev

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning node.next to curr causing cycle.

Assigning node.next to next causing no reversal.

We reverse by pointing current node's next to previous node.

4fill in blank

hard

Fill both blanks to merge the two halves of the list alternately.

DSA Rust

while second.is_some() {
    let mut temp1 = first.as_mut().unwrap().next.take();
    let mut temp2 = second.as_mut().unwrap().next.take();
    first.as_mut().unwrap().next = second;
    second = [1];
    first = [2];
}

Drag options to blanks, or click blank then click option'

Atemp2

Btemp1

Csecond

Dfirst

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning second to first or vice versa causing infinite loop.

Not updating pointers correctly causing broken list.

We move second to temp2 and first to temp1 to continue merging.

5fill in blank

hard

Fill all three blanks to complete the reorder list function in Rust.

DSA Rust

pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return;
    }
    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();
    }
    let mut second = slow.unwrap().next.clone();
    slow.unwrap().next = None;
    let mut prev = None;
    let mut curr = second;
    while let Some(mut node) = curr {
        let next = node.next.take();
        node.next = [1];
        prev = Some(node);
        curr = next;
    }
    let mut first = head.take();
    let mut second = prev;
    while second.is_some() {
        let mut temp1 = first.as_mut().unwrap().next.take();
        let mut temp2 = second.as_mut().unwrap().next.take();
        first.as_mut().unwrap().next = second;
        second = [2];
        first = [3];
    }
    *head = first;
}

Drag options to blanks, or click blank then click option'

Aprev

Btemp2

Ctemp1

Dcurr

Attempts:

3 left

💡 Hint

Common Mistakes

Incorrect reversal causing cycles.

Wrong pointer updates causing broken merge.

Reverse second half by pointing node.next to prev, then merge by updating second to temp2 and first to temp1.

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