Sort a Linked List Using Merge Sort in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new linked list node with the given value.

DSA Rust

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

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

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

Aval

B0

CNone

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using None or 0 instead of the input parameter 'val'.

Assigning 'next' field to 'val'.

The constructor uses the input parameter 'val' to set the node's value.

2fill in blank

medium

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

DSA Rust

fn find_middle(head: &Option<Box<ListNode>>) -> Option<&Box<ListNode>> {
    let mut slow = head.as_ref();
    let mut fast = head.as_ref();
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = [1];
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
    }
    slow
}

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

Aslow.unwrap().next.as_ref()

Bfast.unwrap().next.as_ref()

Cslow = fast.unwrap().next.as_ref()

Dfast = slow.unwrap().next.as_ref()

Attempts:

3 left

💡 Hint

Common Mistakes

Moving the fast pointer one step instead of two.

Moving slow pointer incorrectly or mixing pointers.

The slow pointer moves one step at a time to find the middle node.

3fill in blank

hard

Fix the error in the merge function to correctly merge two sorted linked lists.

DSA Rust

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 {
                node1.next = [1];
                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,
    }
}

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

Amerge(node2.next, Some(node1))

Bmerge(Some(node1), node2.next)

Cmerge(node1.next, Some(node2))

Dmerge(Some(node2), node1.next)

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping parameters incorrectly in recursive merge call.

Passing wrong next pointers.

When node1's value is smaller, we merge node1.next with l2 (Some(node2)).

4fill in blank

hard

Fill both blanks to split the linked list into two halves and recursively sort them.

DSA Rust

fn merge_sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    let mut slow = &head;
    let mut fast = &head;
    let mut prev = None;
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        prev = slow.as_ref();
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }
    let mid = slow.clone();
    if let Some(mut p) = prev.cloned() {
        p.next = None;
    }
    let left = merge_sort(head);
    let right = merge_sort([1]);
    merge(left, [2])
}

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

Amid

Bhead

Cright

Dmid.clone()

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables for recursive calls.

Not splitting the list correctly.

We recursively sort the left half (head) and right half (mid), then merge them.

5fill in blank

hard

Fill all three blanks to complete the merge sort implementation for linked list.

DSA Rust

fn merge_sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    let mut slow = &head;
    let mut fast = &head;
    let mut prev = None;
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        prev = slow.as_ref();
        slow = &slow.as_ref().unwrap().next;
        fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
    }
    let mid = slow.clone();
    if let Some(mut p) = prev.cloned() {
        p.next = [1];
    }
    let left = merge_sort(head);
    let right = merge_sort([2]);
    merge([3], right)
}

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

ANone

Bmid

Cleft

DSome(mid)

Attempts:

3 left

💡 Hint

Common Mistakes

Not breaking the list properly by setting p.next to None.

Mixing left and right variables in recursive calls.

We break the list by setting p.next to None, then recursively sort left and right halves and merge.

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