Merge Two Sorted Linked Lists in DSA Rust

Mental Model

We combine two lists that are already sorted by picking the smallest next item from either list until all items are merged.

Analogy: Imagine two people each have a sorted stack of cards. They reveal the top card from each stack and the smaller card is placed into a new pile. Repeat until both stacks are empty.

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Dry Run Walkthrough

Input: list1: 1->3->5, list2: 2->4->6

Goal: Create one sorted list containing all elements from both lists

Step 1: Compare heads: 1 (list1) and 2 (list2), pick 1

Merged: 1 -> null
List1: 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Why: 1 is smaller, so it goes first in merged list

Step 2: Compare heads: 3 (list1) and 2 (list2), pick 2

Merged: 1 -> 2 -> null
List1: 3 -> 5 -> null
List2: 4 -> 6 -> null

Why: 2 is smaller, so it goes next

Step 3: Compare heads: 3 (list1) and 4 (list2), pick 3

Merged: 1 -> 2 -> 3 -> null
List1: 5 -> null
List2: 4 -> 6 -> null

Why: 3 is smaller, so it goes next

Step 4: Compare heads: 5 (list1) and 4 (list2), pick 4

Merged: 1 -> 2 -> 3 -> 4 -> null
List1: 5 -> null
List2: 6 -> null

Why: 4 is smaller, so it goes next

Step 5: Compare heads: 5 (list1) and 6 (list2), pick 5

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null
List1: null
List2: 6 -> null

Why: 5 is smaller, so it goes next

Step 6: List1 empty, append remaining list2 nodes

Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
List1: null
List2: null

Why: No more nodes in list1, so add all remaining list2 nodes

Result:

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

Annotated Code

DSA Rust

use std::fmt::{self, Display, Formatter};

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

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

struct LinkedList {
    head: Option<Box<ListNode>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn from_vec(vals: Vec<i32>) -> Self {
        let mut list = LinkedList::new();
        for &val in vals.iter().rev() {
            let mut node = Box::new(ListNode::new(val));
            node.next = list.head.take();
            list.head = Some(node);
        }
        list
    }

    fn merge_sorted_lists(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        // Create a dummy node to start the merged list
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;

        // Mutable copies of input lists
        let mut l1 = l1;
        let mut l2 = l2;

        // While both lists have nodes
        while l1.is_some() && l2.is_some() {
            // Compare current nodes
            if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {
                // Attach l1 node to merged list
                tail.next = l1.take();
                tail = tail.next.as_mut().unwrap(); // advance tail
                l1 = tail.next.take(); // advance l1
            } else {
                // Attach l2 node to merged list
                tail.next = l2.take();
                tail = tail.next.as_mut().unwrap(); // advance tail
                l2 = tail.next.take(); // advance l2
            }
        }

        // Attach remaining nodes
        tail.next = if l1.is_some() { l1 } else { l2 };

        dummy.next
    }
}

impl Display for LinkedList {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        let mut curr = &self.head;
        while let Some(node) = curr {
            write!(f, "{} -> ", node.val)?;
            curr = &node.next;
        }
        write!(f, "null")
    }
}

fn main() {
    let list1 = LinkedList::from_vec(vec![1, 3, 5]);
    let list2 = LinkedList::from_vec(vec![2, 4, 6]);

    let merged_head = LinkedList::merge_sorted_lists(list1.head, list2.head);
    let merged_list = LinkedList { head: merged_head };

    println!("{}", merged_list);
}

while l1.is_some() && l2.is_some() {

loop while both lists have nodes to compare

if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {

compare current node values to pick smaller

tail.next = l1.take();

attach smaller node from l1 to merged list

tail = tail.next.as_mut().unwrap();

advance tail pointer to last node in merged list

l1 = tail.next.take();

advance l1 pointer to next node

tail.next = l2.take();

attach smaller node from l2 to merged list

l2 = tail.next.take();

advance l2 pointer to next node

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

attach remaining nodes after one list is empty

Output

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

Complexity Analysis

Time: O(n + m) because we traverse each node in both lists once

Space: O(1) because we rearrange pointers without extra storage

vs Alternative: Compared to concatenating and sorting, this method is faster and uses less memory

Edge Cases

One or both lists empty

Returns the non-empty list or null if both empty

DSA Rust

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

Lists with duplicate values

Duplicates are merged in sorted order without loss

DSA Rust

if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {

Lists with one element each

Merges correctly by comparing single nodes

DSA Rust

while l1.is_some() && l2.is_some() {

When to Use This Pattern

When you see two sorted lists and need one sorted list, use the merge pattern to combine them efficiently by picking the smallest next element.

Common Mistakes

Mistake: Not advancing the pointer of the list from which a node was taken
Fix: After attaching a node, advance that list's pointer to its next node

Mistake: Forgetting to attach remaining nodes after one list is empty
Fix: Attach the leftover nodes from the non-empty list after the main loop

Summary

Merges two sorted linked lists into one sorted linked list.

Use when you have two sorted lists and want a combined sorted list efficiently.

Always pick the smaller head node from either list and advance pointers carefully.

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