Merge Two Sorted Linked Lists in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after merging two sorted linked lists?

Given two sorted linked lists, what is the printed state of the merged linked list?

DSA Rust

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

fn merge_two_lists(
    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_two_lists(next, Some(node2));
                Some(node1)
            } else {
                let next = node2.next.take();
                node2.next = merge_two_lists(Some(node1), next);
                Some(node2)
            }
        }
        (Some(node1), None) => Some(node1),
        (None, Some(node2)) => Some(node2),
        (None, None) => None,
    }
}

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

fn main() {
    let l1 = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 3, next: Some(Box::new(ListNode { val: 5, next: None })) })) }));
    let l2 = Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 4, next: Some(Box::new(ListNode { val: 6, next: None })) })) }));
    let merged = merge_two_lists(l1, l2);
    print_list(&merged);
}

A [1, 3, 5, 2, 4, 6]

B [1, 2, 3, 4, 5, 6]

C [2, 4, 6, 1, 3, 5]

D [6, 5, 4, 3, 2, 1]

💡 Hint

Think about how the merge function compares the head nodes of both lists and recursively merges the rest.

The merge function compares the values at the heads of both lists and picks the smaller one to continue merging. This results in a sorted merged list.

🧠 Conceptual

intermediate

What is the time complexity of merging two sorted linked lists?

If you merge two sorted linked lists of lengths m and n, what is the time complexity of the merge operation?

A O(max(m, n)^2)

B O(m * n)

C O(log(m + n))

D O(m + n)

💡 Hint

Consider how many nodes you visit in total during the merge.

Each node from both lists is visited exactly once during the merge, so the time complexity is linear in the total number of nodes.

🔧 Debug

advanced

What error does this Rust code produce?

Consider this Rust code snippet for merging two sorted linked lists. What error will it produce when compiled?

DSA Rust

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

A cannot assign twice to immutable variable `node1`

B expected struct `Box`, found enum `Option`

C cannot move out of `node1.next` because it is borrowed

D missing lifetime specifier

💡 Hint

Look at how `node1` and `node2` are used after being matched as immutable bindings.

The variables `node1` and `node2` are immutable by default. Trying to assign to their fields causes a compile error about assigning to an immutable variable.

❓ Predict Output

advanced

What is the output of this iterative merge function?

Given two sorted linked lists, what is the printed merged list after running this iterative merge function?

DSA Rust

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

fn merge_two_lists_iter(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode { val: 0, next: None });
    let mut tail = &mut dummy;

    while l1.is_some() && l2.is_some() {
        if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {
            let next = l1.as_mut().unwrap().next.take();
            tail.next = l1;
            l1 = next;
        } else {
            let next = l2.as_mut().unwrap().next.take();
            tail.next = l2;
            l2 = next;
        }
        tail = tail.next.as_mut().unwrap();
    }

    tail.next = if l1.is_some() { l1 } else { l2 };
    dummy.next
}

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

fn main() {
    let l1 = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 4, next: None })) }));
    let l2 = Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 3, next: None })) }));
    let merged = merge_two_lists_iter(l1, l2);
    print_list(&merged);
}

A [1, 4, 2, 3]

B [2, 3, 1, 4]

C [1, 2, 3, 4]

D [4, 3, 2, 1]

💡 Hint

The iterative method picks the smaller node each time and appends it to the merged list.

The function merges nodes in sorted order by comparing heads and appending the smaller one, resulting in a sorted merged list.

🚀 Application

expert

How many nodes are in the merged list after merging these two lists?

List 1 has nodes with values [1, 3, 5, 7, 9]. List 2 has nodes with values [2, 4, 6]. After merging these two sorted linked lists, how many nodes does the merged list contain?

A 8

B 6

C 9

D 7

💡 Hint

Count the total nodes from both lists combined.

The merged list contains all nodes from both lists, so total nodes = 5 + 3 = 8.

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