Merge Two Sorted Linked Lists in DSA Rust - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Start with two sorted lists

↓

Compare heads of both lists

↓

Choose smaller node

↓

Attach chosen node to merged list

↓

Move pointer in chosen list

↓

Repeat until one list is empty

↓

Attach remaining nodes from non-empty list

↓

Return merged sorted list

We compare the first nodes of both lists, pick the smaller one, attach it to the merged list, and move forward. Repeat until all nodes are merged.

Execution Sample

DSA Rust

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

This Rust function merges two sorted linked lists recursively by choosing the smaller head node each time.

Execution Table

Step	Operation	Nodes in List 1	Nodes in List 2	Pointer Changes	Visual State of Merged List
1	Compare heads: 1 vs 2	1 -> 3 -> 5 -> null	2 -> 4 -> 6 -> null	Choose 1 from List 1	1 -> null
2	Compare heads: 3 vs 2	3 -> 5 -> null	2 -> 4 -> 6 -> null	Choose 2 from List 2	1 -> 2 -> null
3	Compare heads: 3 vs 4	3 -> 5 -> null	4 -> 6 -> null	Choose 3 from List 1	1 -> 2 -> 3 -> null
4	Compare heads: 5 vs 4	5 -> null	4 -> 6 -> null	Choose 4 from List 2	1 -> 2 -> 3 -> 4 -> null
5	Compare heads: 5 vs 6	5 -> null	6 -> null	Choose 5 from List 1	1 -> 2 -> 3 -> 4 -> 5 -> null
6	List 1 empty, attach remaining List 2	null	6 -> null	Attach 6	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
7	All nodes merged	null	null	Done	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

💡 Both lists are fully merged; no nodes left to process.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
List1 Pointer	1 -> 3 -> 5 -> null	3 -> 5 -> null	3 -> 5 -> null	5 -> null	5 -> null	null	null	null
List2 Pointer	2 -> 4 -> 6 -> null	2 -> 4 -> 6 -> null	4 -> 6 -> null	4 -> 6 -> null	6 -> null	6 -> null	null	null
Merged List	empty	1 -> null	1 -> 2 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Key Moments - 3 Insights

Why do we move the pointer only in the list from which we took the node?

Because we attach the smaller node from that list to the merged list, so we must advance that list's pointer to the next node. The other list's pointer stays to compare its current node next time. See execution_table steps 1 and 2.

What happens when one list becomes empty before the other?

We attach the remaining nodes of the non-empty list directly to the merged list without further comparisons. This is shown in execution_table step 6.

Why do we use recursion instead of a loop here?

Recursion simplifies the code by handling the merging step-by-step, calling itself with smaller lists until one is empty. Each recursive call attaches one node. This is visible in the code sample and reflected in the stepwise pointer changes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which node was chosen and attached to the merged list?

A Node with value 4 from List 2

B Node with value 2 from List 2

C Node with value 3 from List 1

D Node with value 5 from List 1

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at Step 3 in execution_table.

At which step does List 1 become empty according to variable_tracker?

A After Step 5

B After Step 6

C After Step 4

D After Step 3

💡 Hint

Look at the 'List1 Pointer' row in variable_tracker and find when it becomes 'null'.

If the first node of List 2 was smaller than List 1's, how would the merged list start after Step 1?

A With List 1's first node

B With List 2's first node

C Empty merged list

D Both nodes attached simultaneously

💡 Hint

Refer to the logic in concept_flow and execution_table Step 1 where the smaller node is chosen.

Concept Snapshot

Merge Two Sorted Linked Lists:
- Compare heads of both lists
- Attach smaller node to merged list
- Move pointer in chosen list
- Repeat until one list is empty
- Attach remaining nodes from other list
- Result is a sorted merged list

Full Transcript

This concept merges two sorted linked lists by comparing their head nodes. At each step, the smaller node is chosen and attached to the merged list. The pointer in the chosen list moves forward. This repeats until one list is empty, then the remaining nodes of the other list are attached. The process can be done recursively, as shown in the Rust code sample. The execution table traces each step, showing which node is chosen, how pointers move, and the merged list's state. Variable tracking shows pointer positions after each step. Key moments clarify why only one pointer moves at a time, what happens when a list empties, and why recursion is used. The visual quiz tests understanding of these steps.

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