Merge Two Sorted Lists

Interview guide for Merge Two Sorted Lists with intuition, dry run, C++ code, complexity, and practice problems

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Merge Two Sorted Lists.

1. Intuition

You build the answer in sorted order by always picking the smaller front node. A dummy node makes the code clean because the head stops being a special case.

2. How It Works

Create a dummy node and a tail
Compare the current nodes of both lists
Attach the smaller one to tail
Advance the chosen list and the tail
Attach the remaining nodes

3. Pattern Recognition

Think merge when you see:

two sorted linked lists
merge k lists
divide and conquer on lists

4. Dry Run Example

Input:

l1 = 1 -> 3 -> 5
l2 = 2 -> 4 -> 6

Step-by-step execution:

Pick 1
Pick 2
Pick 3
Continue alternating

Final Output:

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

5. Code (C++)

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  ListNode dummy(0);
  ListNode* tail = &dummy;

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

  tail->next = (l1 != nullptr) ? l1 : l2;
  return dummy.next;
}