Merge Two Sorted Linked Lists in DSA Rust - Deep Dive

Overview - Merge Two Sorted Linked Lists

What is it?

Merging two sorted linked lists means combining them into one sorted linked list. Each input list is already sorted from smallest to largest. The goal is to create a new list that keeps this order without changing the original lists. This helps organize data efficiently when two sorted sequences need to be combined.

Why it matters

Without merging sorted lists, combining sorted data would be slow and complicated. Imagine trying to merge two sorted phone contact lists manually; it would take a lot of time and mistakes. This concept makes combining sorted data fast and easy, which is important in many programs like searching, sorting, and managing data streams.

Where it fits

Before learning this, you should understand what linked lists are and how they work. After mastering merging, you can learn about more complex sorting algorithms, like merge sort, which uses this merging step repeatedly to sort large data efficiently.

Mental Model

Core Idea

Merging two sorted linked lists means picking the smallest current element from either list step-by-step to build one sorted list.

Think of it like...

It's like two friends lining up in order by height and you merge their lines by always choosing the shorter person waiting at the front of either line.

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

Merge process:
Start: Compare 1 and 2, pick 1
Next: Compare 3 and 2, pick 2
Next: Compare 3 and 4, pick 3
Next: Compare 5 and 4, pick 4
Next: Compare 5 and 6, pick 5
Next: Only 6 left, pick 6

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

Build-Up - 7 Steps

1

Foundation

Understanding Linked Lists Basics

Concept: Learn what a linked list is and how nodes connect to form a chain.

A linked list is a chain of nodes. Each node holds a value and a link to the next node. The last node points to nothing (null). For example, a list with values 1, 2, 3 looks like: 1 -> 2 -> 3 -> null. You can move from one node to the next by following these links.

Result

You can represent a sequence of values connected by links, not by indexes like arrays.

Understanding linked lists is key because merging works by moving through these links, not by jumping to positions.

2

Foundation

What Does Sorted Mean in Linked Lists?

Concept: Learn that sorted means values increase step-by-step along the list.

A sorted linked list has values arranged from smallest to largest. For example, 1 -> 3 -> 5 -> null is sorted because 1 < 3 < 5. This order helps us merge two lists efficiently by always comparing the front values.

Result

You know how to check if a list is sorted and why that helps merging.

Knowing the lists are sorted lets us pick the smallest next element without searching the whole list.

3

Intermediate

Step-by-Step Merge Logic

🤔Before reading on: do you think we should pick the smaller or larger value first when merging? Commit to your answer.

Concept: Introduce the idea of comparing front nodes and picking the smaller one to build the merged list.

Start with two pointers at the heads of the two lists. Compare their values. Pick the smaller value node and add it to the merged list. Move that pointer forward. Repeat until one list is empty, then add the rest of the other list.

Result

A new sorted list that contains all nodes from both lists in order.

Understanding this comparison and pointer movement is the heart of merging sorted lists.

4

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: what happens if one list is empty? Will the merge still work correctly?

Concept: Learn how to handle cases when one or both lists are empty or when one finishes before the other.

If one list is empty, the merged list is just the other list. If one list finishes first, append the remaining nodes of the other list directly. This avoids unnecessary comparisons and keeps the merge efficient.

Result

The merge function works correctly for all input cases, including empty lists.

Knowing how to handle these cases prevents bugs and ensures the merge is robust.

5

Intermediate

Implementing Merge in Rust with Ownership

🤔Before reading on: do you think we can just copy nodes in Rust, or do we need to move ownership? Commit to your answer.

Concept: Learn how Rust's ownership rules affect merging linked lists and how to move nodes safely.

In Rust, each node owns its next node. To merge, we take ownership of nodes from the input lists and link them into a new list. We use Option> to represent links. We carefully move nodes without cloning to keep memory safe and efficient.

Result

A Rust function that merges two sorted linked lists by moving nodes, respecting ownership.

Understanding Rust ownership is crucial to write safe and efficient linked list code.

6

Advanced

Optimizing Merge with Dummy Head Node

🤔Before reading on: do you think starting with an empty dummy node helps or complicates the merge? Commit to your answer.

Concept: Use a dummy head node to simplify linking nodes during merge.

Create a dummy node before the merged list starts. Use a pointer to build the list by linking nodes after the dummy. This avoids special cases for the first node and makes code cleaner. At the end, return dummy.next as the merged list head.

Result

Cleaner and easier-to-read merge code that handles all cases uniformly.

Using a dummy node is a common pattern that reduces complexity and bugs in linked list operations.

7

Expert

In-Place Merge Without Extra Allocation

🤔Before reading on: can we merge two linked lists without creating new nodes or extra memory? Commit to your answer.

Concept: Merge by rearranging existing nodes' links without allocating new nodes.

Instead of creating new nodes, adjust the next pointers of existing nodes to form the merged list. This saves memory and improves performance. The algorithm carefully moves pointers to avoid losing nodes and maintains sorted order.

Result

An efficient merge that reuses existing nodes, suitable for performance-critical applications.

Knowing how to merge in-place is a powerful skill that optimizes memory and speed in real-world systems.

Under the Hood

The merge works by maintaining two pointers, each pointing to the current node in the two input lists. At each step, the algorithm compares the values at these pointers, selects the smaller node, and links it to the merged list. The pointer of the chosen node advances to the next node. This continues until one list is exhausted, then the remaining nodes of the other list are linked directly. In Rust, this involves moving ownership of nodes using Option> and carefully updating links without cloning or invalid references.

Why designed this way?

This approach was designed to leverage the sorted property of input lists, allowing a linear-time merge without extra sorting. Using pointers and ownership movement in Rust ensures memory safety and efficiency. Alternatives like copying nodes or using arrays would waste memory or lose the benefits of linked list structure. The dummy node pattern simplifies edge cases, making the code easier to maintain.

┌─────────────┐       ┌─────────────┐
│ List1 Head  │       │ List2 Head  │
│ (Node A)    │       │ (Node B)    │
└─────┬───────┘       └─────┬───────┘
      │                     │
      ▼                     ▼
  Compare values         Compare values
      │                     │
      └─────┐         ┌─────┘
            ▼         ▼
       Pick smaller node
            │
            ▼
     Link to merged list
            │
            ▼
     Move pointer forward
            │
            ▼
    Repeat until one list ends
            │
            ▼
    Append remaining nodes
            │
            ▼
      Merged Sorted List

Myth Busters - 4 Common Misconceptions

Quick: Do you think merging two sorted linked lists requires creating new nodes? Commit to yes or no.

Common Belief: Merging means creating a brand new list with new nodes copied from the originals.

Reality: Merging can be done by rearranging the existing nodes' links without creating new nodes.

Why it matters: Creating new nodes wastes memory and time, while in-place merging is more efficient and practical.

Quick: Do you think the merged list can be unsorted if input lists are sorted? Commit to yes or no.

Common Belief: Merging two sorted lists might produce an unsorted list if not careful.

Reality: If the merge algorithm always picks the smaller current node, the merged list remains sorted.

Why it matters: Incorrect merging logic can break sorting, causing bugs in programs relying on sorted data.

Quick: Do you think the order of input lists affects the merged result? Commit to yes or no.

Common Belief: Swapping the two input lists changes the merged list order.

Reality: The merged list is always sorted regardless of input order because the algorithm compares values at each step.

Why it matters: Understanding this prevents confusion and incorrect assumptions about input order.

Quick: Do you think Rust allows freely copying nodes during merge? Commit to yes or no.

Common Belief: In Rust, nodes can be copied easily during merge without ownership issues.

Reality: Rust enforces ownership rules, so nodes must be moved, not copied, to avoid memory errors.

Why it matters: Ignoring ownership leads to compile errors or unsafe code, blocking correct Rust implementations.

Expert Zone

1

The dummy head node pattern not only simplifies code but also improves performance by reducing conditional checks during linking.

2

In Rust, using Option> allows safe ownership transfer of nodes, but requires careful handling of None cases to avoid panics.

3

In-place merging avoids extra memory allocation but requires precise pointer manipulation to prevent losing nodes or creating cycles.

When NOT to use

Avoid this merge approach if the input lists are not sorted, as it will produce incorrect results. For unsorted lists, consider sorting first or using other data structures like heaps or balanced trees. Also, if random access is needed, arrays or vectors are better than linked lists.

Production Patterns

In real-world systems, merging sorted linked lists is used in merge sort implementations, streaming data merges, and database query optimizations. Rust implementations often use in-place merging with dummy nodes for performance and safety. This pattern also appears in functional programming with immutable lists, where new lists are created instead of in-place changes.

Connections

Merge Sort Algorithm

Builds-on

Understanding how to merge two sorted lists is the core step in merge sort, a powerful sorting algorithm that divides and conquers data.

Rust Ownership Model

Builds-on

Knowing Rust's ownership and borrowing rules is essential to implement linked list merges safely and efficiently without memory errors.

Queue Data Structure

Same pattern

Merging sorted lists by picking the smallest front element is similar to how priority queues dequeue the highest priority item, showing a shared selection pattern.

Common Pitfalls

#1 Losing nodes by not updating pointers correctly.

Wrong approach:

fn merge(mut l1: Option>, mut l2: Option>) -> Option> {
if l1.is_none() { return l2; }
if l2.is_none() { return l1; }
if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {
let mut head = l1;
head.as_mut().unwrap().next = merge(head.as_mut().unwrap().next.take(), l2);
head
} else {
let mut head = l2;
head.as_mut().unwrap().next = merge(l1, head.as_mut().unwrap().next.take());
head
}
}

Correct approach:

fn merge(mut l1: Option>, mut l2: Option>) -> Option> {
let mut dummy = Box::new(Node { 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
}

Root cause:

Not carefully taking ownership and updating next pointers causes nodes to be lost or duplicated, breaking the list.

#2 Trying to copy nodes instead of moving ownership in Rust.

Wrong approach:

fn merge(l1: Option>, l2: Option>) -> Option> {
// Attempt to clone nodes
let mut v1 = l1.clone();
let mut v2 = l2.clone();
// ...
}

Correct approach:

fn merge(mut l1: Option>, mut l2: Option>) -> Option> {
// Move nodes without cloning
// ...
}

Root cause:

Rust's ownership model forbids cloning Box without explicit clone implementations; moving ownership is required.

#3 Not handling empty lists correctly, causing panics.

Wrong approach:

fn merge(l1: Option>, l2: Option>) -> Option> {
if l1.as_ref().unwrap().val < l2.as_ref().unwrap().val {
// ...
} else {
// ...
}
}

Correct approach:

fn merge(l1: Option>, l2: Option>) -> Option> {
if l1.is_none() { return l2; }
if l2.is_none() { return l1; }
// ...
}

Root cause:

Calling unwrap() on None causes runtime panic; must check for None before unwrap.

Key Takeaways

Merging two sorted linked lists means picking the smallest current node from either list step-by-step to build a new sorted list.

Using a dummy head node simplifies the merge process by avoiding special cases for the first node.

In Rust, ownership rules require moving nodes carefully without cloning to maintain memory safety during merge.

Handling edge cases like empty lists or one list finishing early is essential for a robust merge function.

In-place merging reuses existing nodes and is more efficient than creating new nodes, important for performance-critical applications.

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