Merge Two Sorted Linked Lists in DSA C++ - Deep Dive

Overview - Merge Two Sorted Linked Lists

What is it?

Merging two sorted linked lists means combining them into one sorted linked list. Each input list is already sorted from smallest to largest. The goal is to create a new list that keeps this order without sorting again. This helps in many problems where data is already sorted and needs to be combined efficiently.

Why it matters

Without merging sorted lists efficiently, programs would waste time sorting combined data repeatedly. This would slow down tasks like searching, organizing, or processing data streams. Merging sorted lists saves time and memory by reusing the order already present. It is a building block for bigger algorithms like sorting large data or managing real-time data.

Where it fits

Before this, learners should understand what linked lists are and how to traverse them. After mastering merging, learners can explore sorting algorithms like merge sort or advanced data structures like balanced trees. This topic connects basic linked list operations to more complex algorithmic patterns.

Mental Model

Core Idea

Merging two sorted linked lists means picking the smallest current element from either list step-by-step to build one sorted list.

Think of it like...

Imagine two people each holding a sorted deck of cards. They reveal the top card from their decks and the smaller card is placed into a new pile. They repeat this until both decks are empty, resulting in one sorted pile.

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

Merge process:
Start: Compare 1 and 2 -> pick 1
Next: Compare 3 and 2 -> pick 2
Next: Compare 3 and 4 -> pick 3
Next: Compare 5 and 4 -> pick 4
Next: Compare 5 and 6 -> pick 5
Next: Only 6 left -> pick 6

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

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Basics

Concept: Learn what a linked list is and how nodes connect to form a chain.

A linked list is a chain of nodes where each node holds data and a pointer to the next node. The last node points to null, marking the end. You can move through the list by following these pointers one by one.

Result

You can traverse a linked list from start to end, visiting each node in order.

Understanding linked lists is essential because merging relies on moving through two lists node by node.

2

Foundation

What Does Sorted Mean in Linked Lists

Concept: Recognize that sorted linked lists have nodes arranged from smallest to largest values.

A sorted linked list means each node's value is less than or equal to the next node's value. This order helps us merge efficiently by comparing only the current nodes of each list.

Result

You can predict which node comes next by comparing current nodes, without scanning the whole list.

Knowing the lists are sorted lets us merge by simple comparisons, avoiding extra sorting.

3

Intermediate

Step-by-Step Merge Logic

🤔Before reading on: do you think we should compare all nodes at once or just the current nodes? Commit to your answer.

Concept: Introduce the idea of comparing only the current nodes of each list to decide which node to add next.

Start with pointers at the heads of both lists. Compare the values at these pointers. Attach the smaller node to the merged list and move that pointer forward. Repeat until one list ends, then attach the remaining nodes of the other list.

Result

A new linked list that contains all nodes from both lists in sorted order.

Comparing only current nodes keeps the merge efficient and simple, avoiding unnecessary checks.

4

Intermediate

Using a Dummy Node for Cleaner Code

🤔Before reading on: do you think we need special cases for the first node of the merged list? Commit to your answer.

Concept: Use a dummy node as a fixed starting point to simplify attaching nodes without special cases.

Create a dummy node before the merged list starts. Use a pointer to build the merged list from this dummy. This avoids checking if the merged list is empty when adding nodes. After merging, return dummy's next node as the real head.

Result

Simpler code that handles all nodes uniformly, including the first one.

Using a dummy node removes edge cases and makes the merge logic cleaner and less error-prone.

5

Intermediate

Iterative vs Recursive Merge Approaches

🤔Before reading on: do you think recursion or iteration is simpler for merging? Commit to your answer.

Concept: Explore two ways to merge: looping through nodes (iteration) or calling the merge function within itself (recursion).

Iterative merges use loops and pointers to build the merged list step-by-step. Recursive merges compare heads and call themselves on the rest of the lists, building the merged list as the call stack unwinds.

Result

Both methods produce the same merged list, but recursion uses more memory due to call stack.

Knowing both methods helps choose the best approach depending on constraints like memory or code clarity.

6

Advanced

Handling Edge Cases in Merging

🤔Before reading on: what happens if one list is empty? Commit to your answer.

Concept: Learn how to handle cases where one or both lists are empty or have different lengths.

If one list is empty, return the other list as is. If lists have different lengths, after one ends, attach the remaining nodes of the other list. This ensures no nodes are lost.

Result

The merged list correctly contains all nodes even if inputs differ in size or are empty.

Handling edge cases prevents bugs and ensures the merge works in all real-world scenarios.

7

Expert

Optimizing Merge for Production Use

🤔Before reading on: do you think merging modifies input lists or creates new nodes? Commit to your answer.

Concept: Understand that merging can be done by reusing existing nodes without creating new ones, saving memory and time.

Instead of creating new nodes, adjust the next pointers of existing nodes to build the merged list. This in-place merge avoids extra memory allocation and improves performance. Be careful to not lose references to nodes during pointer changes.

Result

An efficient merge that reuses nodes, suitable for large data or performance-critical systems.

Knowing how to merge in-place is key for writing high-performance code and understanding pointer manipulation deeply.

Under the Hood

Merging works by maintaining two pointers, each pointing to the current node of the two input lists. At each step, the algorithm compares the values at these pointers and links the smaller node to the merged list. The pointer of the chosen node advances to the next node. This continues until one list is exhausted, then the remaining nodes of the other list are linked directly. Internally, this manipulates the 'next' pointers of nodes without copying data, making it memory efficient.

Why designed this way?

This approach was designed to leverage the sorted property of input lists, avoiding the need to sort again. It minimizes comparisons and memory usage by reusing nodes. Alternatives like concatenating and sorting would be slower and use more memory. The dummy node technique was introduced to simplify edge cases and reduce code complexity.

┌─────────────┐       ┌─────────────┐
│ List1 Head  │       │ List2 Head  │
└─────┬───────┘       └─────┬───────┘
      │                     │
      ▼                     ▼
  [Node1] -> [Node3] -> ...  [Node2] -> [Node4] -> ...
      │                     │
      └─────┐         ┌─────┘
            ▼         ▼
        Compare values
            │
            ▼
      Attach smaller node to merged list
            │
            ▼
      Move pointer forward in chosen list
            │
            ▼
      Repeat until one list ends
            │
            ▼
      Attach remaining nodes from other list
            │
            ▼
      Merged sorted linked list head

Myth Busters - 3 Common Misconceptions

Quick: Do you think merging two sorted lists always creates new nodes? Commit yes or no.

Common Belief: Merging two sorted linked lists means creating a brand new list with new nodes.

Reality: Merging can be done by rearranging the existing nodes' pointers without creating new nodes.

Why it matters: Creating new nodes wastes memory and time, especially for large lists. Reusing nodes is more efficient and common in practice.

Quick: Do you think the merged list can be unsorted if input lists are sorted? Commit yes or no.

Common Belief: If both input lists are sorted, the merged list might still be unsorted due to pointer errors.

Reality: If merged correctly by always picking the smaller current node, the merged list is guaranteed sorted.

Why it matters: Incorrect merging logic can break the sorted order, causing bugs in later algorithms relying on sorted data.

Quick: Do you think recursion is always better than iteration for merging? Commit yes or no.

Common Belief: Recursive merging is simpler and always better than iterative merging.

Reality: Recursive merging uses more memory due to call stack and can cause stack overflow on large lists; iteration is safer for production.

Why it matters: Choosing recursion blindly can cause crashes or inefficiency in real systems.

Expert Zone

1

Reusing nodes during merge requires careful pointer updates to avoid losing parts of the list or creating cycles.

2

The dummy node technique is a subtle but powerful pattern that simplifies linked list manipulations beyond merging.

3

Recursive merge implementations implicitly use the call stack as a data structure, which can be replaced by explicit stacks for better control.

When NOT to use

Avoid merging linked lists if the lists are not sorted; instead, consider sorting first or using data structures like balanced trees or heaps for merging unsorted data.

Production Patterns

In production, merging sorted linked lists is used in external sorting algorithms, merging data streams, and implementing priority queues. Efficient in-place merging is preferred to minimize memory overhead.

Connections

Merge Sort Algorithm

Merge sort uses merging of sorted lists as its core step to sort larger lists.

Understanding merging linked lists deeply helps grasp how merge sort efficiently sorts data by dividing and conquering.

Pointer Manipulation in Data Structures

Merging linked lists requires precise pointer updates, a fundamental skill in many linked data structures.

Mastering pointer changes in merging builds confidence for working with complex structures like trees and graphs.

Real-Time Data Stream Processing

Merging sorted linked lists models combining sorted data streams in real-time systems.

Knowing merging helps design systems that handle live data efficiently, like merging sensor readings or logs.

Common Pitfalls

#1 Losing nodes by overwriting pointers without saving next references.

Wrong approach:

while (list1 && list2) {
if (list1->val < list2->val) {
merged->next = list1;
merged = merged->next;
list1 = list1->next;
} else {
merged->next = list2;
merged = merged->next;
list2 = list2->next;
}
// Missing saving next pointers before reassigning
}
// Attach remaining nodes
merged->next = list1 ? list1 : list2;

Correct approach:

ListNode dummy(0);
ListNode* merged = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
merged->next = list1;
list1 = list1->next;
} else {
merged->next = list2;
list2 = list2->next;
}
merged = merged->next;
}
merged->next = list1 ? list1 : list2;

Root cause:

Not updating the merged pointer after attaching nodes causes pointer loss and breaks the list.

#2 Not handling empty input lists causing null pointer errors.

Wrong approach:

if (list1->val < list2->val) {
// proceed without checking if list1 or list2 is null
}

Correct approach:

if (!list1) return list2;
if (!list2) return list1;
if (list1->val < list2->val) {
// safe to proceed
}

Root cause:

Assuming inputs are always non-empty leads to runtime crashes.

#3 Creating new nodes unnecessarily instead of reusing existing ones.

Wrong approach:

while (list1 && list2) {
if (list1->val < list2->val) {
merged->next = new ListNode(list1->val);
list1 = list1->next;
} else {
merged->next = new ListNode(list2->val);
list2 = list2->next;
}
merged = merged->next;
}

Correct approach:

while (list1 && list2) {
if (list1->val < list2->val) {
merged->next = list1;
list1 = list1->next;
} else {
merged->next = list2;
list2 = list2->next;
}
merged = merged->next;
}

Root cause:

Not realizing nodes can be reused leads to inefficient memory use.

Key Takeaways

Merging two sorted linked lists means building a new sorted list by repeatedly choosing the smaller current node from either list.

Using a dummy node simplifies the code by removing special cases for the first node in the merged list.

Both iterative and recursive methods work, but iteration is safer for large lists due to memory use.

Reusing existing nodes during merge is more efficient than creating new nodes.

Handling edge cases like empty lists or different lengths ensures the merge works correctly in all situations.

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