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

↓

Smaller node

↓

Move current and chosen list pointer forward

↓

Repeat comparison until one list ends

↓

Attach remaining nodes of non-empty list

↓

Return dummy.next as merged list head

We create a dummy node to start the merged list, then repeatedly pick the smaller node from the heads of the two lists, attach it, and move pointers until one list is empty. Finally, attach the leftover nodes.

Execution Sample

DSA C

ListNode* merge(ListNode* l1, ListNode* l2) {
  ListNode dummy = {0, NULL};
  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 choosing the smaller head node each time and linking nodes to form a new sorted 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 to current.next	dummy(0) -> 1 -> NULL	current = 1, l1 moves to 3	dummy(0) -> 1 -> NULL
3	Compare l1(3) and l2(2), attach l2 to current.next	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 to current.next	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 to current.next	dummy(0) -> 1 -> 2 -> 3 -> 4 -> NULL	current = 4, l2 moves to NULL	dummy(0) -> 1 -> 2 -> 3 -> 4 -> NULL
6	l2 is NULL, attach remaining 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	Return dummy.next as merged list head	1 -> 2 -> 3 -> 4 -> 5 -> NULL	No pointer changes	1 -> 2 -> 3 -> 4 -> 5 -> NULL

💡 Loop ends when one list is empty; remaining nodes attached to merged list.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
l1	1 -> 3 -> 5 -> NULL	3 -> 5 -> NULL	3 -> 5 -> NULL	5 -> NULL	5 -> NULL	NULL	NULL
l2	2 -> 4 -> NULL	2 -> 4 -> NULL	4 -> NULL	4 -> NULL	NULL	NULL	NULL
current	dummy(0)	1	2	3	4	5	5
merged list	empty	dummy(0) -> 1 -> NULL	dummy(0) -> 1 -> 2 -> NULL	dummy(0) -> 1 -> 2 -> 3 -> NULL	dummy(0) -> 1 -> 2 -> 3 -> 4 -> NULL	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL	1 -> 2 -> 3 -> 4 -> 5 -> NULL

Key Moments - 3 Insights

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

Using a dummy node simplifies linking nodes because it avoids special cases for the head. As seen in step 1 and 7, dummy.next points to the merged list head, so we always have a stable starting point.

What happens when one list becomes empty before the other?

When either l1 or l2 becomes NULL (step 5), we attach the remaining nodes of the other list directly to current->next. This ensures no nodes are lost and the merged list remains sorted.

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

Moving current forward (steps 2-5) keeps track of the last node in the merged list, so the next chosen node can be linked correctly. Without moving current, nodes would overwrite the same next pointer.

Visual Quiz - 3 Questions

Look at the execution table at step 4. Which node does current point to after attaching?

A Node with value 2

B Node with value 3

C Node with value 4

D Dummy node

💡 Hint

Check the 'Pointer Changes' column at step 4 in the execution_table.

At which step does the loop end because one list becomes empty?

A Step 7

B Step 6

C Step 5

D Step 3

💡 Hint

Look for when l2 moves to NULL in the variable_tracker and execution_table.

If l1 started with values all greater than l2, how would the merged list start?

A With nodes from l2 first

B Alternating nodes from l1 and l2

C With nodes from l1 first

D Empty list

💡 Hint

Recall the comparison step picks the smaller node each time, as shown in the concept_flow.

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->next
- Move current and chosen list pointer forward
- Repeat until one list ends
- Attach remaining nodes
- Return dummy.next as merged list head

Full Transcript

To merge two sorted linked lists, we start by creating a dummy node to simplify linking. We use a pointer 'current' starting at dummy. Then, we compare the values at the heads of both lists. The smaller node is attached to current->next, and we move current and that list's pointer forward. We repeat this until one list is empty. After that, we attach the remaining nodes of the other list to current->next. Finally, we return dummy.next, which points to the head of the merged sorted list. This approach avoids special cases and ensures all nodes are included in order.

Practice

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

easy

A. To create a new sorted linked list containing all elements from both lists

B. To reverse both linked lists

C. To find the maximum element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merge operation

   Merging two sorted linked lists means combining their elements 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 in order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option A

4. Quick Check:

   Merge = combine sorted lists [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merge reverses lists
• Confusing merge with finding max element
• Assuming merge removes duplicates

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; struct Node* next; };

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

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

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

Solution

1. Step 1: Check struct syntax for linked list node

   In C, a node contains data and a pointer to the next node. The pointer must be declared as 'struct Node* next;'.

2. Step 2: Identify correct declaration

   struct Node { int data; struct Node* next; }; correctly declares 'struct Node' with 'int data' and 'struct Node* next;'. struct Node { int data; Node* next; }; misses 'struct' keyword before Node*, struct Node { int data; struct Node next; }; incorrectly uses 'struct Node next;' (not a pointer), and struct Node { int data; struct Node* prev; }; uses 'prev' which is for doubly linked lists.

3. Final Answer:

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

4. Quick Check:

   Node struct needs pointer to next node [OK]

Hint: Node pointer must use 'struct Node*' in C [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node*
• Using node instead of pointer for next
• Confusing singly linked list with doubly linked list

3. What will be the output linked list after merging these two sorted linked lists?

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

Assuming the merge function merges correctly.

medium

A. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> NULL

B. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> NULL

C. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

D. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Solution

1. Step 1: Compare elements from both lists in order

   Start with heads: 1 (List1) and 2 (List2). 1 < 2, so 1 goes first. Then compare 3 and 2, 2 < 3, so 2 goes next. Continue this way to merge in sorted order.

2. Step 2: Build merged list step-by-step

   Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL -> Option C

4. Quick Check:

   Merge keeps sorted order [OK]

Hint: Pick smaller node each step to merge sorted lists [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Reversing the order accidentally
• Skipping nodes during merge

4. Consider this buggy merge function snippet in C:

struct Node* merge(struct Node* l1, struct 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;
    }
}

What is the main issue if this function is called with two sorted lists?

medium

A. It reverses the merged list

B. It merges lists correctly without issues

C. It loses nodes when one list is empty

D. It causes infinite recursion when lists have equal elements

Solution

1. Step 1: Analyze base cases

   If one list is empty (!l1 or !l2), it correctly returns the other list.

2. Step 2: Analyze recursive case

   If l1->data < l2->data, it sets l1->next to the merge of the rest and returns l1. Otherwise, sets l2->next to merge(l1, l2->next) and returns l2. However, when l1->data == l2->data, the else branch is taken repeatedly without advancing l1, causing infinite recursion.

3. Final Answer:

   It causes infinite recursion when lists have equal elements -> Option D

4. Quick Check:

   Equal elements cause infinite recursion due to no advancement in l1 [OK]

Hint: Recursive merge must handle equal elements to avoid infinite recursion [OK]

Common Mistakes:

• Thinking equal elements cause infinite recursion
• Believing it loses nodes on empty lists
• Assuming it reverses the list

5. You have two sorted linked lists:
List1: 1 -> 4 -> 7 -> NULL
List2: 2 -> 4 -> 6 -> 8 -> NULL

Write the merged sorted linked list after merging them and removing duplicate values.

hard

A. 1 -> 4 -> 7 -> 2 -> 4 -> 6 -> 8 -> NULL

B. 1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL

C. 1 -> 2 -> 4 -> 4 -> 6 -> 7 -> 8 -> NULL

D. 1 -> 2 -> 6 -> 7 -> 8 -> NULL

Solution

1. Step 1: Merge lists in sorted order

   Merge elements: 1, 2, 4, 4, 6, 7, 8.

2. Step 2: Remove duplicate values

   Remove one of the duplicate 4's to get: 1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL.

3. Final Answer:

   1 -> 2 -> 4 -> 6 -> 7 -> 8 -> NULL -> Option B

4. Quick Check:

   Merge + remove duplicates = sorted unique list [OK]

Hint: Merge then skip duplicates for unique sorted list [OK]

Common Mistakes:

• Leaving duplicates in merged list
• Appending lists without sorting
• Removing unique elements by mistake