Merge Two Sorted Linked Lists in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Rust

let mut dummy = ListNode::new([1]);

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

ANone

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using None instead of a numeric value.

Using 1 or -1 which are valid but not standard for dummy node.

The dummy node is usually initialized with 0 as a placeholder value.

2fill in blank

medium

Complete the code to move the pointer to the next node in the merged list.

DSA Rust

current = current.[1].as_mut().unwrap();

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

Aprev

Bnext

Cchild

Dlink

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' which points backward.

Using 'child' or 'link' which are not standard field names.

In a linked list, the next node is accessed via the 'next' field.

3fill in blank

hard

Fix the error in the comparison to merge nodes from list1 and list2.

DSA Rust

if list1.as_ref().unwrap().val [1] list2.as_ref().unwrap().val {

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

A<

B==

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which picks the larger value first.

Using '==' or '!=' which do not order nodes.

We want to pick the smaller value node first, so use '<' to compare.

4fill in blank

hard

Fill both blanks to correctly assign the next node and advance the pointer.

DSA Rust

current.[1] = list1.take();
list1 = current.[2].as_mut().unwrap().next.take();

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

Anext

Bprev

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' or 'child' which are incorrect fields.

Mixing up the order of assignment and pointer movement.

We assign to 'next' and then move list1 to the next node via 'next'.

5fill in blank

hard

Fill all three blanks to return the merged list skipping the dummy node.

DSA Rust

return dummy.[1].take();

// dummy is a [2] node
// .[3] points to the first real node

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

Anext

BListNode

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Returning dummy instead of dummy.next.

Confusing 'prev' with 'next' pointer.

We return dummy.next because dummy is a ListNode and next points to the merged list start.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. Reverse both linked lists

B. Remove duplicates from both lists

C. Create a new sorted linked list containing all elements from both lists

D. Sort each list separately without merging

Solution

1. Step 1: Understand the problem

   Merging two sorted linked lists means combining them into one list that remains sorted.

2. Step 2: Identify the goal

   The goal is to create a new sorted linked list that contains all elements from both input lists.

3. Final Answer:

   Create a new sorted linked list containing all elements from both lists -> Option C

4. Quick Check:

   Merging = Combined sorted list [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merging means reversing lists
• Trying to sort lists separately without merging
• Confusing merging with removing duplicates

2. Which Rust code snippet correctly declares a singly linked list node struct for merging?

easy

A. struct ListNode { val: i32, next: 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 Rust linked list node

   Rust needs heap allocation for recursive types, so next must be Option.

2. Step 2: Check each option

   struct ListNode { val: i32, next: Option } uses Option, which is correct. Others use references or direct types causing errors.

3. Final Answer:

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

4. Quick Check:

   Use Option for linked list nodes [OK]

Hint: Use Option for recursive linked list nodes in Rust [OK]

Common Mistakes:

• Using direct ListNode type for next causes infinite size error
• Using references without lifetimes causes borrow errors
• Using Option<ListNode> misses boxing needed for recursion

3. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what is the merged list? How does the merge function handle this edge case?

let l1: Option = None;
let l2 = Some(Box::new(ListNode { val: 0, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 4, next: None })) })) }));

let merged = merge_two_lists(l1, l2);

easy

A. 0 -> 2 -> 4 -> null

B. null

C. 0 -> null

D. 2 -> 4 -> null

Solution

1. Step 1: Check input lists

   l1 is None (empty), l2 is 0 -> 2 -> 4 -> null.

2. Step 2: Merge function returns non-empty list

   When one list is None, function returns the other list as is.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option A

4. Quick Check:

   Empty + list = list unchanged [OK]

Hint: If one list empty, merged list is the other list [OK]

Common Mistakes:

• Returning null when one list is empty
• Trying to merge empty list nodes incorrectly
• Losing nodes from non-empty list

4. What is the output linked list after merging these two sorted lists? List1: 1 -> 3 -> 5 -> null List2: 2 -> 4 -> 6 -> null

fn merge_two_lists(l1: Option, l2: Option) -> Option {
    match (l1, l2) {
        (None, None) => None,
        (Some(node), None) | (None, Some(node)) => Some(node),
        (Some(mut n1), Some(mut n2)) => {
            if n1.val < n2.val {
                n1.next = merge_two_lists(n1.next.take(), Some(n2));
                Some(n1)
            } else {
                n2.next = merge_two_lists(Some(n1), n2.next.take());
                Some(n2)
            }
        }
    }
}

medium

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

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

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

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

Solution

1. Step 1: Trace first comparison

   Compare 1 and 2: 1 < 2, so 1 is first node.

2. Step 2: Recursively merge remaining lists

   Next merge 3->5 and 2->4->6. 2 < 3, so 2 next, then 3, 4, 5, 6.

3. Final Answer:

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

4. Quick Check:

   Sorted merge = 1,2,3,4,5,6 [OK]

Hint: Pick smaller head each step to merge sorted lists [OK]

Common Mistakes:

• Appending lists instead of merging sorted
• Not updating next pointers correctly
• Mixing order of nodes in merged list

5. Identify the bug in this Rust merge function and select the fix:

fn merge_two_lists(l1: Option, l2: Option) -> Option {
    match (l1, l2) {
        (None, None) => None,
        (Some(node), None) => Some(node),
        (None, Some(node)) => Some(node),
        (Some(mut n1), Some(mut n2)) => {
            if n1.val <= n2.val {
                n1.next = merge_two_lists(n1.next, Some(n2));
                Some(n1)
            } else {
                n2.next = merge_two_lists(Some(n1), n2.next);
                Some(n2)
            }
        }
    }
}

medium

A. Remove match and use if-else only

B. Change if condition to n1.val < n2.val

C. Replace Some(mut n1) with &mut n1

D. Use n1.next.take() and n2.next.take() to avoid borrowing errors

Solution

1. Step 1: Identify ownership issue

   n1.next and n2.next are Options; assigning without take() causes borrowing errors.

2. Step 2: Fix by using take()

   Using n1.next.take() and n2.next.take() moves ownership out safely for recursion.

3. Final Answer:

   Use n1.next.take() and n2.next.take() to avoid borrowing errors -> Option D

4. Quick Check:

   Use take() to move Option ownership [OK]

Hint: Use .take() to move Option values safely in Rust [OK]

Common Mistakes:

• Not using take() causes borrow checker errors
• Changing comparison operator unnecessarily
• Using references incorrectly in pattern matching