Merge Two Sorted Linked Lists in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted linked lists

What is the printed state of the merged linked list after merging these two sorted lists?

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

DSA C++

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

Node* mergeLists(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}

// After merging, print the list
void printList(Node* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "null" << std::endl;
}

// Assume lists are created and merged as above

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

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

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

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

💡 Hint

Think about how two sorted lists merge by always choosing the smaller current element.

The merge function compares the heads of both lists and picks the smaller value first, then recursively merges the rest. This results in a fully sorted merged list.

❓ Predict Output

intermediate

Output of iterative merge of two sorted linked lists

What is the printed state of the merged linked list after merging these two sorted lists using an iterative approach?

List 1: 1 -> 4 -> 7 -> null
List 2: 2 -> 3 -> 6 -> null

DSA C++

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

Node* mergeListsIterative(Node* l1, Node* l2) {
    Node dummy(0);
    Node* tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// After merging, print the list
void printList(Node* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "null" << std::endl;
}

// Assume lists are created and merged as above

A 2 -> 3 -> 6 -> 1 -> 4 -> 7 -> null

B 1 -> 4 -> 7 -> 2 -> 3 -> 6 -> null

C 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> null

D 1 -> 2 -> 4 -> 3 -> 6 -> 7 -> null

💡 Hint

The iterative method also picks the smaller node each time, building the merged list step by step.

The iterative merge uses a dummy node and a tail pointer to append the smaller node from either list until one list is empty, then appends the rest.

🔧 Debug

advanced

Identify the error in this merge function

What error will this merge function cause when merging two sorted linked lists?

DSA C++

Node* mergeLists(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val <= l2->val) {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
    return nullptr;
}

A No error; function works correctly

B Stack overflow due to infinite recursion

C Null pointer dereference when l1 or l2 is null

D Memory leak due to missing delete calls

💡 Hint

Check the base cases and recursive calls carefully.

The function correctly handles base cases and merges recursively without infinite loops or null dereferences. No memory leak occurs as nodes are reused.

❓ Predict Output

advanced

Output after merging lists with duplicate values

What is the printed state of the merged linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> 7 -> null
List 2: 3 -> 5 -> 8 -> null

DSA C++

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

Node* mergeLists(Node* l1, Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}

// After merging, print the list
void printList(Node* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "null" << std::endl;
}

// Assume lists are created and merged as above

A 1 -> 3 -> 3 -> 5 -> 5 -> 7 -> 8 -> null

B 1 -> 3 -> 5 -> 7 -> 3 -> 5 -> 8 -> null

C 1 -> 3 -> 5 -> 3 -> 5 -> 7 -> 8 -> null

D 3 -> 3 -> 5 -> 5 -> 7 -> 8 -> 1 -> null

💡 Hint

Duplicates appear in order as they come from both lists.

The merge function preserves order and includes duplicates from both lists in sorted order.

🧠 Conceptual

expert

Time complexity of merging two sorted linked lists

What is the time complexity of merging two sorted linked lists of lengths m and n?

A O(m * n)

B O(m + n)

C O(max(m, n)^2)

D O(log(m + n))

💡 Hint

Consider how many nodes are visited during the merge.

Each node from both lists is visited exactly once during the merge, so the time is proportional to the sum of their lengths.

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