Sort a Linked List Using Merge Sort in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a Linked List

What is the printed state of the linked list after applying merge sort on the list 4 -> 2 -> 1 -> 3 -> null?

DSA Rust

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

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

fn merge_sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    fn split(mut head: Option<Box<ListNode>>) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
        if head.is_none() || head.as_ref().unwrap().next.is_none() {
            return (head, None);
        }
        let mut slow = &mut head;
        let mut fast = &head.as_ref().unwrap().next;
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            slow = &mut slow.as_mut().unwrap().next;
            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
        }
        let mid = slow.as_mut().unwrap().next.take();
        (head, mid)
    }

    fn merge(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match (l1, l2) {
            (Some(mut node1), Some(mut node2)) => {
                if node1.val < node2.val {
                    let next = node1.next.take();
                    node1.next = merge(next, Some(node2));
                    Some(node1)
                } else {
                    let next = node2.next.take();
                    node2.next = merge(Some(node1), next);
                    Some(node2)
                }
            }
            (Some(node1), None) => Some(node1),
            (None, Some(node2)) => Some(node2),
            (None, None) => None,
        }
    }

    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    let (left, right) = split(head);
    let sorted_left = merge_sort(left);
    let sorted_right = merge_sort(right);
    merge(sorted_left, sorted_right)
}

fn main() {
    let node4 = ListNode { val: 3, next: None };
    let node3 = ListNode { val: 1, next: Some(Box::new(node4)) };
    let node2 = ListNode { val: 2, next: Some(Box::new(node3)) };
    let node1 = ListNode { val: 4, next: Some(Box::new(node2)) };
    let head = Some(Box::new(node1));

    let sorted_head = merge_sort(head);
    print_list(&sorted_head);
}

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

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

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

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

💡 Hint

Merge sort splits the list into halves and merges sorted halves.

Merge sort on linked list sorts nodes in ascending order. The input list 4 -> 2 -> 1 -> 3 is sorted to 1 -> 2 -> 3 -> 4.

🧠 Conceptual

intermediate

Why use Merge Sort for Linked Lists?

Which reason best explains why merge sort is preferred for sorting linked lists over quicksort or heapsort?

A Merge sort uses less memory than quicksort and heapsort on arrays.

B Merge sort modifies the original list nodes to arrays before sorting.

C Merge sort does not require random access and works efficiently with linked list pointers.

D Merge sort is faster than quicksort in all cases for linked lists.

💡 Hint

Think about how linked lists store data and how merge sort works.

Merge sort works well with linked lists because it only rearranges pointers and does not need random access, unlike quicksort or heapsort.

🔧 Debug

advanced

Identify the Bug in Linked List Merge Function

What error will occur when running this merge function for two sorted linked lists? fn merge(l1: Option>, l2: Option>) -> Option> { match (l1, l2) { (Some(mut node1), Some(mut node2)) => { if node1.val <= node2.val { node1.next = merge(node1.next, Some(node2)); Some(node1) } else { node2.next = merge(Some(node1), node2.next); Some(node2) } } (Some(node1), None) => Some(node1), (None, Some(node2)) => Some(node2), (None, None) => None, } }

A Compilation error due to moving out of borrowed content

B Stack overflow due to infinite recursion

C Runtime panic due to null pointer dereference

D No error, function works correctly

💡 Hint

Check how ownership and borrowing are handled with mutable nodes.

The code tries to move out of a mutable reference (node1.next) which is not allowed, causing a compilation error.

❓ Predict Output

advanced

Result of Splitting a Linked List

Given the linked list 5 -> 8 -> 3 -> 7 -> null, what are the two lists after the split function is called?

DSA Rust

fn split(mut head: Option<Box<ListNode>>) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return (head, None);
    }
    let mut slow = &mut head;
    let mut fast = &head.as_ref().unwrap().next;
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = &mut slow.as_mut().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }
    let mid = slow.as_mut().unwrap().next.take();
    (head, mid)
}

// Initial list: 5 -> 8 -> 3 -> 7 -> null

A First list: 5 -> 8 -> 3 -> 7 -> null, Second list: null

B First list: 5 -> 8 -> 3 -> null, Second list: 7 -> null

C First list: 5 -> null, Second list: 8 -> 3 -> 7 -> null

D First list: 5 -> 8 -> null, Second list: 3 -> 7 -> null

💡 Hint

The slow pointer stops before the middle node, splitting the list in half.

The split function divides the list into two halves: first half 5 -> 8 and second half 3 -> 7.

🚀 Application

expert

Number of Recursive Calls in Merge Sort

For a linked list with 8 nodes, how many total recursive calls to merge_sort will be made during the full sort process?

A 8

B 15

C 7

D 16

💡 Hint

Think about how merge sort splits the list into halves recursively until single nodes.

Merge sort on 8 nodes splits into 8 single nodes (base cases) plus all intermediate calls, totaling 15 calls.

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Merge sort is faster than quicksort in all cases.

B. Merge sort uses less memory than quicksort.

C. Merge sort does not require random access, which suits linked lists well.

D. Merge sort sorts the list in place without extra space.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, unlike arrays.

2. Step 2: Compare sorting algorithms

   Merge sort works well with sequential access by splitting and merging, while quicksort relies on random access for partitioning.

3. Final Answer:

   Merge sort does not require random access, which suits linked lists well. -> Option C

4. Quick Check:

   Linked list + merge sort = no random access needed [OK]

Hint: Merge sort fits linked lists because it avoids random access [OK]

Common Mistakes:

• Thinking quicksort is always faster
• Assuming merge sort sorts in place without extra space
• Confusing memory usage between merge sort and quicksort

2. Which Rust code snippet correctly defines a singly linked list node struct for merge sort?

easy

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

B. struct ListNode { val: i32, next: Option }

C. struct ListNode { val: i32, next: &ListNode }

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

Solution

1. Step 1: Understand ownership in Rust linked lists

   Rust requires ownership for heap data; Box<T> owns heap data, Option allows None or a node.

2. Step 2: Analyze options

   struct ListNode { val: i32, next: Option } uses Option which is correct for nullable next pointer. Others use references without ownership or missing Option.

3. Final Answer:

   struct ListNode { val: i32, next: Option } -> Option B

4. Quick Check:

   Rust linked list node uses Option [OK]

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

Common Mistakes:

• Using references (&) without lifetime management
• Omitting Option for nullable next pointer
• Using Box<T> without Option causing no null

3. Given the following linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted list after applying merge sort?

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

   Split 4->2->1->3 into 4->2 and 1->3.

2. Step 2: Recursively sort and merge

   Sort halves: 4->2 becomes 2->4, 1->3 becomes 1->3. Merge sorted halves: 1->2->3->4.

3. Final Answer:

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

4. Quick Check:

   Sorted ascending linked list = 1->2->3->4 [OK]

Hint: Merge sort splits and merges sorted halves for linked lists [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Confusing order of merged nodes

4. In the Rust merge sort implementation for linked lists, which mistake causes infinite recursion?

medium

A. Using Box instead of Rc for next pointers

B. Using a mutable reference instead of ownership for nodes

C. Sorting the list without splitting it

D. Not updating the next pointer to None when splitting the list

Solution

1. Step 1: Understand splitting in merge sort

   Splitting requires breaking the list into two halves by setting the middle node's next pointer to None.

2. Step 2: Identify infinite recursion cause

   If next pointer is not set to None, recursive calls never reach base case, causing infinite recursion.

3. Final Answer:

   Not updating the next pointer to None when splitting the list -> Option D

4. Quick Check:

   Broken split causes infinite recursion [OK]

Hint: Set middle.next = None to stop recursion [OK]

Common Mistakes:

• Forgetting to break the list at midpoint
• Confusing Box and Rc usage
• Misusing references causing borrow errors

5. You have a linked list with duplicate values: 5 -> 3 -> 5 -> 2 -> 3 -> null. After applying merge sort, what is the correct sorted list?

hard

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

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

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

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

Solution

1. Step 1: Recognize duplicates in the list

   The list contains duplicates: two 5s and two 3s.

2. Step 2: Apply merge sort preserving duplicates

   Merge sort sorts all nodes including duplicates, resulting in ascending order with duplicates preserved: 2->3->3->5->5.

3. Final Answer:

   2 -> 3 -> 3 -> 5 -> 5 -> null -> Option A

4. Quick Check:

   Sorted list keeps duplicates in order [OK]

Hint: Merge sort keeps duplicates sorted in order [OK]

Common Mistakes:

• Removing duplicates by mistake
• Sorting incorrectly ignoring duplicates
• Confusing output order with duplicates