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 head 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 compare the heads of the two lists, attach the smaller node to the merged list, and move pointers forward until all nodes are merged.

Execution Sample

DSA C#

ListNode MergeTwoLists(ListNode l1, ListNode l2) {
  ListNode dummy = new ListNode(0);
  ListNode current = dummy;
  while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
      current.next = l1; l1 = l1.next;
    } else {
      current.next = l2; l2 = l2.next;
    }
    current = current.next;
  }
  current.next = 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	dummy(0)	dummy -> null, current = dummy	0(dummy) -> null
2	Compare l1(1) and l2(2)	1 -> 3 -> 5, 2 -> 4 -> 6	current.next = l1(1), l1 = 3	0(dummy) -> 1 -> null
3	Move current to 1	3 -> 5, 2 -> 4 -> 6	current = 1	0(dummy) -> 1 -> null
4	Compare l1(3) and l2(2)	3 -> 5, 2 -> 4 -> 6	current.next = l2(2), l2 = 4	0(dummy) -> 1 -> 2 -> null
5	Move current to 2	3 -> 5, 4 -> 6	current = 2	0(dummy) -> 1 -> 2 -> null
6	Compare l1(3) and l2(4)	3 -> 5, 4 -> 6	current.next = l1(3), l1 = 5	0(dummy) -> 1 -> 2 -> 3 -> null
7	Move current to 3	5, 4 -> 6	current = 3	0(dummy) -> 1 -> 2 -> 3 -> null
8	Compare l1(5) and l2(4)	5, 4 -> 6	current.next = l2(4), l2 = 6	0(dummy) -> 1 -> 2 -> 3 -> 4 -> null
9	Move current to 4	5, 6	current = 4	0(dummy) -> 1 -> 2 -> 3 -> 4 -> null
10	Compare l1(5) and l2(6)	5, 6	current.next = l1(5), l1 = null	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
11	Move current to 5	null, 6	current = 5	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
12	l1 is null, attach remaining l2(6)	null, 6	current.next = l2(6), l2 = null	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
13	Move current to 6	null, null	current = 6	0(dummy) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
14	Return dummy.next as merged list head	Merged list: 1 -> 2 -> 3 -> 4 -> 5 -> 6	dummy.next points to 1	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

💡 Both l1 and l2 are null, all nodes merged

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	Final
l1	1 -> 3 -> 5	3 -> 5	3 -> 5	5	5	5	null	null	null	null	null	null	null	null
l2	2 -> 4 -> 6	2 -> 4 -> 6	4 -> 6	4 -> 6	4 -> 6	6	6	6	null	null	null	null	null	null
current	dummy(0)	1	2	3	4	5	5	6	6	6	6	6	6	6
dummy.next	null	1	1	1	1	1	1	1	1	1	1	1	1	1

Key Moments - 3 Insights

Why do we use a dummy node instead of starting with one of the input lists?

Using a dummy node simplifies the code by providing a fixed starting point for the merged list. This avoids special cases for the first node. See execution_table step 1 where dummy is created and current points to it.

What happens when one list becomes empty before the other?

When one list is empty, we attach the remaining nodes of the other list directly to the merged list. This is shown in execution_table step 12 where l1 is null and remaining l2 nodes are attached.

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

Moving current forward ensures the next attached node is linked correctly. Without moving current, the list would not grow properly. See steps 3, 5, 7, 9, 11 where current moves after attaching nodes.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which node is attached to current.next?

A Node with value 3 from l1

B Node with value 2 from l2

C Node with value 4 from l2

D Node with value 5 from l1

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 in execution_table

At which step does l1 become null?

A Step 12

B Step 14

C Step 10

D Step 8

💡 Hint

Look at the 'l1' variable values in variable_tracker after each step

If we swapped the comparison to 'if (l1.val <= l2.val)', how would the merged list change?

A It would remain the same

B Nodes with equal values from l1 would come before l2

C Nodes with equal values from l2 would come before l1

D The merged list would be reversed

💡 Hint

Think about how the comparison affects which node is chosen when values are equal

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list
- Compare heads of both lists
- Attach smaller node to merged list
- Move pointers forward
- Attach remaining nodes when one list ends
- Return dummy.next as merged list head

Full Transcript

To merge two sorted linked lists, we start by creating a dummy node that acts as the fixed starting point of the merged list. We use a pointer called current to track the last node in the merged list. We then compare the values at the heads of both input lists. The smaller node is attached to current.next, and we move the pointer of that list forward. We also move current forward to the newly attached node. This process repeats until one of the lists becomes empty. At that point, we attach the remaining nodes of the other list to the merged list. Finally, we return dummy.next, which points to the head of the merged sorted list. This approach avoids special cases and keeps the code simple and clean.

Practice

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

easy

A. Remove duplicates from both lists

B. Create a new sorted linked list containing all elements from both lists

C. Reverse both linked lists

D. Sort each list individually without merging

Solution

1. Step 1: Understand the problem goal

   The goal is to combine two sorted linked lists into one sorted linked list.

2. Step 2: Clarify the expected output

   The output should be a single linked list that maintains sorted order and contains all nodes from both input lists.

3. Final Answer:

   Create a new sorted linked list containing all elements from both lists -> Option B

4. Quick Check:

   Merge means combine sorted lists into one sorted list [OK]

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

Common Mistakes:

• Thinking merge means reversing lists
• Trying to sort lists separately without merging
• Removing duplicates instead of merging

2. Which of the following is the correct C# syntax to declare a node class for a singly linked list used in merging?

easy

A. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

B. public struct Node { int val; Node next; }

C. public class Node { public int val; public Node next; public Node(int x) { val = x; next = null; } }

D. public class Node { int val; int next; public Node(int x) { val = x; next = 0; } }

Solution

1. Step 1: Check class declaration and access modifiers

   public class Node { public int val; public Node next; public Node(int x) { val = x; next = null; } } correctly declares a public class with public fields and a constructor initializing values.

2. Step 2: Verify field types and initialization

   public class Node { public int val; public Node next; public Node(int x) { val = x; next = null; } } uses 'int val' and 'Node next' with proper initialization; others miss public or use wrong types.

3. Final Answer:

   public class Node { public int val; public Node next; public Node(int x) { val = x; next = null; } } -> Option C

4. Quick Check:

   Correct class with public fields and constructor [OK]

Hint: Node class needs public fields and constructor for linked list [OK]

Common Mistakes:

• Missing public keyword causing access errors
• Using struct instead of class for linked list node
• Incorrect type for next pointer

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

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

Assuming the merge function merges correctly.

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 first nodes of both lists

   1 (List1) < 2 (List2), so 1 is first in merged list.

2. Step 2: Continue comparing nodes in order

   Next compare 3 and 2, 2 is smaller, then 3 and 4, 3 is smaller, then 5 and 4, 4 is smaller, then 5 and 6, 5 is smaller, finally 6.

3. Final Answer:

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

4. Quick Check:

   Merge sorted lists by picking smaller node each step [OK]

Hint: Pick smaller node from heads repeatedly to merge [OK]

Common Mistakes:

• Appending one list entirely before the other
• Not maintaining sorted order
• Mixing node order incorrectly

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

public Node Merge(Node l1, Node l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = Merge(l1.next, l2);
        return l1;
    } else {
        l2.next = Merge(l1, l2.next);
        return l2;
    }
}

medium

A. No error; the code correctly merges two sorted linked lists

B. Missing base case for empty lists

C. Incorrect comparison operator used

D. The function does not handle cycles in lists

Solution

1. Step 1: Analyze base cases

   Code returns the other list if one is null, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Code compares values and recursively merges the rest, correctly linking nodes in sorted order.

3. Final Answer:

   No error; the code correctly merges two sorted linked lists -> Option A

4. Quick Check:

   Recursive merge with base cases and correct comparisons [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Incorrect base case handling
• Wrong comparison operator

5. You have two sorted linked lists:
List1: 1 -> 4 -> 5 -> null
List2: 1 -> 3 -> 4 -> null

After merging, what is the correct merged list?
Also, explain why duplicates appear and how the merge handles them.

hard

A. 1 -> 1 -> 4 -> 3 -> 4 -> 5 -> null

B. 1 -> 3 -> 4 -> 5 -> null

C. 1 -> 4 -> 5 -> 3 -> 4 -> 1 -> null

D. 1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null

Solution

1. Step 1: Merge nodes in sorted order including duplicates

   Both lists have '1' and '4' values; merge keeps all nodes, so duplicates appear in order.

2. Step 2: Explain duplicate handling

   Merge does not remove duplicates; it links nodes as they appear, preserving duplicates in sorted order.

3. Final Answer:

   1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null -> Option D

4. Quick Check:

   Duplicates kept; merge preserves all nodes sorted [OK]

Hint: Merge keeps duplicates; just link nodes in sorted order [OK]

Common Mistakes:

• Removing duplicates mistakenly
• Mixing node order
• Appending lists without sorting