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 both are empty.

Analogy: Imagine merging two sorted decks of cards by always taking the top card from the deck that has the smaller card on top.

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

Dry Run Walkthrough

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

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

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

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

Why: We pick the smaller element to keep merged list sorted

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

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

Why: Next smallest element is 2 from list2

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

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

Why: Pick smaller element 3 from list1

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

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

Why: Pick smaller element 4 from list2

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

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

Why: Pick smaller element 5 from list1

Step 6: List1 empty, append remaining list2 elements

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

Why: No more elements in list1, append rest of list2

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // dummy node to start merged list
    ListNode* tail = &dummy; // tail points to last node in merged list

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            tail->next = l1; // attach l1 node
            l1 = l1->next; // advance l1
        } else {
            tail->next = l2; // attach l2 node
            l2 = l2->next; // advance l2
        }
        tail = tail->next; // move tail forward
    }

    // attach remaining nodes if any
    if (l1 != nullptr) tail->next = l1;
    else tail->next = l2;

    return dummy.next; // head of merged list
}

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << " -> null" << endl;
}

int main() {
    // Create list1: 1 -> 3 -> 5 -> null
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    // Create list2: 2 -> 4 -> 6 -> null
    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    ListNode* merged = mergeTwoLists(l1, l2);
    printList(merged);

    return 0;
}

while (l1 != nullptr && l2 != nullptr) {

loop until one list is empty

if (l1->val < l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; }

attach smaller node and advance that list

tail = tail->next;

move tail pointer forward to last node

if (l1 != nullptr) tail->next = l1; else tail->next = l2;

attach remaining nodes after one list ends

return dummy.next;

return head of merged list skipping dummy

Output

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

Complexity Analysis

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

Space: O(1) because we only rearrange pointers without extra storage

vs Alternative: Compared to creating a new list and copying values, this approach is more space efficient and faster since it reuses existing nodes

Edge Cases

One or both lists empty

Returns the non-empty list or null if both empty

DSA C++

while (l1 != nullptr && l2 != nullptr) {

Lists with duplicate values

Duplicates are merged preserving order

DSA C++

if (l1->val < l2->val) {

Lists of different lengths

Remaining nodes of longer list appended after shorter ends

DSA C++

if (l1 != nullptr) tail->next = l1; else tail->next = l2;

When to Use This Pattern

When you see two sorted lists and need one sorted list, use the merge pattern by picking smaller front elements repeatedly.

Common Mistakes

Mistake: Not advancing the tail pointer after attaching a node
Fix: Always move tail forward after attaching a node to keep track of the merged list end

Mistake: Forgetting to attach remaining nodes after one list ends
Fix: After the loop, attach the leftover nodes from the non-empty list

Summary

Merges two sorted linked lists into one sorted linked list by choosing the smaller head node repeatedly.

Use when you have two sorted lists and want to combine them efficiently into one sorted list.

The key is to always pick the smaller current node and move pointers forward until all nodes are merged.

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