Merge Two Sorted Linked Lists in DSA C++ - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Create dummy node

↓

Set current pointer to dummy

↓

Compare heads of both lists

↓

Attach smaller node to current

↓

Move current and chosen list pointer forward

↓

Repeat comparison until one list ends

↓

Attach remaining nodes of non-empty list

↓

Return merged list starting after dummy

Start with a dummy node and a current pointer. Compare the heads of both lists, attach the smaller node to current, move pointers forward, repeat until one list ends, then attach remaining nodes.

Execution Sample

DSA C++

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            current->next = l1; l1 = l1->next;
        } else {
            current->next = l2; l2 = l2->next;
        }
        current = current->next;
    }
    current->next = l1 ? l1 : l2;
    return dummy.next;
}

This code merges two sorted linked lists by comparing nodes and linking the smaller one to the merged list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create dummy node and set current to dummy	dummy(0) -> null	current = dummy	dummy(0) -> null
2	Compare l1(1) and l2(2), attach l1(1)	dummy(0) -> 1 -> null	current = 1, l1 moves to 3	dummy(0) -> 1 -> null
3	Compare l1(3) and l2(2), attach l2(2)	dummy(0) -> 1 -> 2 -> null	current = 2, l2 moves to 4	dummy(0) -> 1 -> 2 -> null
4	Compare l1(3) and l2(4), attach l1(3)	dummy(0) -> 1 -> 2 -> 3 -> null	current = 3, l1 moves to 5	dummy(0) -> 1 -> 2 -> 3 -> null
5	Compare l1(5) and l2(4), attach l2(4)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> null	current = 4, l2 moves to 6	dummy(0) -> 1 -> 2 -> 3 -> 4 -> null
6	Compare l1(5) and l2(6), attach l1(5)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null	current = 5, l1 moves to null	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
7	l1 is null, attach remaining l2(6)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	current(5)->next = l2(6)	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
8	Return merged list starting after dummy	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	No pointer changes	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

💡 l1 is null, remaining l2 attached to current->next, merging complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
l1	1->3->5	3->5	3->5	5	5	null	null	null
l2	2->4->6	2->4->6	4->6	4->6	6	6	6	6
current	dummy(0)	1	2	3	4	5	5	5

Key Moments - 3 Insights

Why do we use a dummy node instead of starting directly with l1 or l2?

The dummy node simplifies linking nodes without checking if the merged list is empty. See execution_table step 1 where dummy is created to start the merged list.

Why do we move the current pointer after attaching a node?

Moving current forward ensures the next attached node links correctly. See steps 2-7 in execution_table where current moves to the newly attached node each time.

What happens when one list becomes empty before the other?

We attach the remaining nodes of the non-empty list directly. See step 7 where l1 is null, so remaining l2 nodes are attached.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node is attached to the merged list?

A Node with value 3 from l1

B Node with value 4 from l2

C Node with value 2 from l2

D Node with value 5 from l1

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 4 in execution_table

At which step does the pointer 'l1' become null?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'l1' row in variable_tracker to see when it becomes null

If l1 started with 0 instead of 1, how would the merged list start?

A With 0 as the first node

B With 1 as the first node

C With 2 as the first node

D With dummy node value 0

💡 Hint

The merged list starts with the smaller node between l1 and l2, see execution_table steps 2 and 8

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list
- Compare heads of both lists
- Attach smaller node to current
- Move current and chosen list pointer forward
- Repeat until one list ends
- Attach remaining nodes
- Return merged list after dummy

Full Transcript

To merge two sorted linked lists, we start by creating a dummy node to simplify the process. We keep a current pointer at the dummy. Then, we compare the values at the heads of both lists. We attach the smaller node to current and move the current pointer and the chosen list pointer forward. We repeat this until one list is empty. Then, we attach the remaining nodes of the other list. Finally, we return the merged list starting after the dummy node. This approach ensures the merged list is sorted and easy to build without special cases for the first node.

Practice

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

easy

A. Sort each list separately before merging

B. Reverse the order of nodes in both lists

C. Combine nodes from both lists maintaining sorted order

D. Remove duplicate nodes from both lists

Solution

1. Step 1: Understand the merge operation

   Merging means combining two lists into one while keeping the order sorted.

2. Step 2: Maintain sorted order during merge

   We pick the smaller node from the heads of both lists repeatedly to keep the merged list sorted.

3. Final Answer:

   Combine nodes from both lists maintaining sorted order -> Option C

4. Quick Check:

   Merge = Combine sorted lists [OK]

Hint: Always pick the smaller node first to keep order [OK]

Common Mistakes:

• Trying to reverse lists instead of merging
• Sorting lists again after merging
• Ignoring order and just concatenating

2. Which of the following is the correct way to declare a node structure for a singly linked list in C++?

easy

A. struct Node { int data; Node next; };

B. class Node { int data; Node next; };

C. class Node { int data; Node* next; };

D. struct Node { int data; Node* next; };

Solution

1. Step 1: Understand node structure in C++

   A node should have data and a pointer to the next node.

2. Step 2: Check pointer usage

   Using Node* next is correct to point to the next node; Node next would cause infinite size error.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option D

4. Quick Check:

   Node pointer = Node* next [OK]

Hint: Use pointers for next node in linked list [OK]

Common Mistakes:

• Using object instead of pointer for next node
• Missing semicolon after struct
• Using class without access specifier

3. What will be the output linked list after merging these two sorted lists?
List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Using a standard merge algorithm?

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. 1 -> 2 -> 4 -> 3 -> 5 -> 6 -> null

Solution

1. Step 1: Compare heads of both lists

   Start with 1 (List1) and 2 (List2). 1 is smaller, so first node is 1.

2. Step 2: Continue picking smaller nodes

   Next compare 3 and 2, pick 2; then 3 and 4, pick 3; then 5 and 4, pick 4; then 5 and 6, pick 5; finally 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 node repeatedly [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Mixing node order incorrectly
• Skipping nodes during merge

4. Given the following code snippet to merge two sorted linked lists, what is the error?

Node* merge(Node* l1, Node* l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1->data < l2->data) {
    l1->next = merge(l1->next, l2);
    return l1;
  } else {
    l2->next = merge(l1, l2->next);
    return l2;
  }
}

medium

A. No error, code correctly merges two sorted lists

B. Missing base case for empty lists

C. Incorrect comparison operator used

D. Function does not handle cyclic lists

Solution

1. Step 1: Check base cases

   Code returns the other list if one is empty, which is correct.

2. Step 2: Check recursive merge logic

   It compares data correctly and recursively merges the rest, returning the smaller node.

3. Final Answer:

   No error, code correctly merges two sorted lists -> Option A

4. Quick Check:

   Recursive merge logic correct [OK]

Hint: Check base cases and recursion carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Wrong base case conditions
• Using wrong pointers in recursion

5. You have two sorted linked lists:
List1: 1 -> 4 -> 5 -> 7 -> null
List2: 2 -> 3 -> 6 -> 8 -> 9 -> null
Write the merged list after merging them. Then, if you want to remove duplicates from the merged list, what will be the final list?
Assume duplicates can appear after merge.

hard

A. Merged: 1 -> 4 -> 5 -> 7 -> 2 -> 3 -> 6 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

B. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

C. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> null

D. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 4 -> 5 -> 7 -> 2 -> 3 -> 6 -> 8 -> 9 -> null

Solution

1. Step 1: Merge both sorted lists

   Pick nodes in order: 1,2,3,4,5,6,7,8,9 forming a sorted merged list.

2. Step 2: Remove duplicates if any

   Since all values are unique, the list remains the same after removing duplicates.

3. Final Answer:

   Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null -> Option B

4. Quick Check:

   Sorted merge with unique values [OK]

Hint: Merge sorted, then remove duplicates if any [OK]

Common Mistakes:

• Concatenating lists without sorting
• Assuming duplicates always exist
• Removing nodes incorrectly