Merge Two Sorted Lists

You are given the heads of two singly linked lists, list1 and list2. Each list is already sorted in non-decreasing order, and either one may be empty.

Combine them into one linked list that is also sorted in non-decreasing order, and return its head. Build the result by relinking the existing nodes (changing their next pointers) rather than copying values into new nodes.

In the examples a linked list is written as the array of its values from head to tail, so [] stands for an empty list (a null head).

Example 1

Example 2

Example 3

Constraints

• Each list has between 0 and 200 nodes.
• -104 <= Node.val <= 104
• Both lists are sorted in non-decreasing order.

Pattern Path · Linked Lists · problem 66 of 169

Start simple

Copy every value into an array, sort it and build a brand-new list: O((n + m) log(n + m)) time and O(n + m) extra space, ignoring that the inputs are already sorted.

The key idea

Because both lists are sorted, the smallest value not yet placed is always at the front of one of the two lists. So the merge is a sequence of tiny decisions: compare the two front nodes, move the smaller one onto the result, repeat.

Keep a tail pointer to the last node of the result so that appending is O(1). A dummy node placed before the real head lets the very first append work exactly like every other one; at the end the answer is dummy.next.

As soon as one list is exhausted, every node left in the other list is already sorted and at least as large as everything placed so far, so you can link the whole remainder with a single pointer assignment instead of walking it.

Using <= when comparing keeps equal values in their original relative order (a stable merge). No nodes are allocated apart from the dummy, so the extra space is constant.

Complexity

• Time: O(n + m)
• Space: O(1)

Python

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode()  # placeholder before the real head
        tail = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        # At most one list still has nodes, and they are all large enough to go last.
        tail.next = list1 if list1 else list2
        return dummy.next

JavaScript

var mergeTwoLists = function(list1, list2) {
  const dummy = new ListNode(); // placeholder before the real head
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  // At most one list still has nodes, and they are all large enough to go last.
  tail.next = list1 || list2;
  return dummy.next;
};

What the interviewer is checking

This checks careful pointer manipulation: keeping track of a tail, not losing the rest of a list, and handling empty inputs without a pile of special cases. It is also the building block of merge sort on lists.

Mistakes to avoid

• Forgetting to attach the leftover nodes once one list is exhausted.
• Returning the dummy node instead of dummy.next.
• Advancing a list pointer after overwriting tail.next, which can make you lose the rest of that list.
• Special-casing an empty list badly and returning null when the other list still has nodes.

Follow-ups to expect

• How would you merge k sorted lists? (Min-heap of current heads, O(N log k).)
• Write it recursively: what does it cost? (O(n + m) call-stack depth.)
• What if both lists were sorted in descending order? (Flip the comparison.)

In real software

The merge step of external sorting combines sorted runs from disk this way, and databases use the same idea in merge joins and when compacting sorted log segments.

Practice next