Merge Two Sorted Linked Lists in DSA C#

Mental Model

We combine two sorted lists by always picking the smaller front item from either list until all items are merged.

Analogy: Imagine merging two lines of people sorted by height into one line, always letting the shorter person step forward first.

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

Dry Run Walkthrough

Input: list1: 1 -> 3 -> 5, list2: 2 -> 4 -> 6

Goal: Create one sorted list containing all elements from both lists in order

Step 1: Compare heads: 1 (list1) vs 2 (list2), pick 1

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

Why: 1 is smaller, so it goes first in merged list

Step 2: Compare heads: 3 (list1) vs 2 (list2), pick 2

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

Why: 2 is smaller, so it goes next

Step 3: Compare heads: 3 (list1) vs 4 (list2), pick 3

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

Why: 3 is smaller, so it goes next

Step 4: Compare heads: 5 (list1) vs 4 (list2), pick 4

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

Why: 4 is smaller, so it goes next

Step 5: Compare heads: 5 (list1) vs 6 (list2), pick 5

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

Why: 5 is smaller, so it goes next

Step 6: List1 empty, append remaining list2 nodes

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

Why: No more nodes in list1, so add all remaining nodes from list2

Result:

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

Annotated Code

DSA C#

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public static ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode current = dummy;
        
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1; // attach smaller node
                list1 = list1.next;   // move list1 forward
            } else {
                current.next = list2; // attach smaller node
                list2 = list2.next;   // move list2 forward
            }
            current = current.next;   // move current forward
        }
        
        // attach remaining nodes if any
        current.next = list1 ?? list2;
        
        return dummy.next;
    }

    public static void PrintList(ListNode head) {
        while (head != null) {
            Console.Write(head.val);
            if (head.next != null) Console.Write(" -> ");
            head = head.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        // Create list1: 1 -> 3 -> 5 -> null
        ListNode list1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        // Create list2: 2 -> 4 -> 6 -> null
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6)));

        ListNode merged = MergeTwoLists(list1, list2);
        PrintList(merged);
    }
}

while (list1 != null && list2 != null) {

continue merging while both lists have nodes

if (list1.val < list2.val) {

compare current nodes to pick smaller one

current.next = list1; // attach smaller node

link smaller node to merged list

list1 = list1.next; // move list1 forward

advance pointer in list1 after attaching node

current = current.next; // move current forward

advance merged list pointer to last node

current.next = list1 ?? list2;

attach remaining nodes after one list ends

Output

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

Complexity Analysis

Time: O(n + m) because we traverse each node in both lists once

Space: O(1) because we only use a few pointers, no extra list

vs Alternative: Compared to concatenating then sorting (O((n+m) log(n+m))), this is faster and uses less space

Edge Cases

One or both lists are empty

Returns the non-empty list or null if both empty

DSA C#

while (list1 != null && list2 != null) {

Lists with duplicate values

Duplicates are merged in order preserving sorting

DSA C#

if (list1.val < list2.val) {

Lists of different lengths

Remaining nodes of longer list appended after shorter ends

DSA C#

current.next = list1 ?? list2;

When to Use This Pattern

When you see two sorted lists and need one sorted list, use the merge pattern to combine them efficiently by picking smaller front nodes.

Common Mistakes

Mistake: Not advancing the current pointer after attaching a node
Fix: Add 'current = current.next;' after attaching a node to keep merged list updated

Mistake: Forgetting to attach remaining nodes after one list ends
Fix: Use 'current.next = list1 ?? list2;' after the loop to add leftover nodes

Summary

Merges two sorted linked lists into one sorted linked list.

Use when you have two sorted lists and want to combine them without sorting again.

Always pick the smaller node from the front of either list and move forward until all nodes are merged.

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