Merge Two Sorted Linked Lists in DSA C# - Build from Scratch

Merge Two Sorted Linked Lists

📖 Scenario: You are working on a contact app that keeps two separate sorted lists of contacts by their ID numbers. You want to combine these two lists into one sorted list so you can show all contacts in order.

🎯 Goal: Build a program that merges two sorted linked lists into one sorted linked list.

📋 What You'll Learn

Create two sorted linked lists with exact values

Create a helper variable to track the start of the merged list

Write the logic to merge the two sorted linked lists

Print the merged linked list in order

💡 Why This Matters

🌍 Real World

Merging sorted lists is common in apps that combine data from multiple sources, like contacts, messages, or events.

💼 Career

Understanding linked lists and merging algorithms is important for software engineering roles involving data structures and efficient data processing.

1

Create two sorted linked lists

Create a linked list called list1 with nodes containing values 1, 3, and 5. Create another linked list called list2 with nodes containing values 2, 4, and 6. Use the provided ListNode class.

DSA C#

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

class Program
{
    static void Main(string[] args)
    {
        // Create list1 with nodes 1 -> 3 -> 5
        // Create list2 with nodes 2 -> 4 -> 6
        // Your code here
    }
}

Hint

Use the ListNode constructor to link nodes by passing the next node as the second argument.

2

Create a dummy head for the merged list

Create a variable called dummy as a new ListNode with value 0. Create a variable called current and set it equal to dummy. This will help track the start and current position of the merged list.

DSA C#

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

class Program
{
    static void Main(string[] args)
    {
        ListNode list1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6)));

        // Create dummy head and current pointer
        // Your code here
    }
}

Hint

The dummy node helps to easily return the head of the merged list later.

3

Merge the two sorted linked lists

Use a while loop that runs while both list1 and list2 are not null. Inside the loop, compare list1.val and list2.val. Attach the smaller node to current.next and move that list forward. Move current forward as well. After the loop, attach the remaining nodes from list1 or list2 to current.next.

DSA C#

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

class Program
{
    static void Main(string[] args)
    {
        ListNode list1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6)));

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Merge list1 and list2
        // Your code here
    }
}

Hint

Use a loop to pick the smaller node from the two lists and attach it to the merged list. After the loop, attach the leftover nodes.

4

Print the merged linked list

Create a variable called node and set it to dummy.next. Use a while loop to traverse the merged list. Inside the loop, print the value of node.val followed by " -> ". Move node to node.next. After the loop, print "null" to mark the end.

DSA C#

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

class Program
{
    static void Main(string[] args)
    {
        ListNode list1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6)));

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                current.next = list1;
                list1 = list1.next;
            }
            else
            {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        if (list1 != null)
        {
            current.next = list1;
        }
        else
        {
            current.next = list2;
        }

        // Print merged list
        // Your code here
    }
}

Hint

Traverse from dummy.next and print each node's value followed by " -> ". End with "null".

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