Merge Two Sorted Lists

Difficulty: Easy

Problem

Two linked lists, list1 and list2, are each sorted in ascending order. Join them into a single sorted list by relinking the existing nodes rather than creating new ones, and return the head of the result.

Example

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: At each step, take the smaller of the two current head nodes: 1 (from list1), 1 (from list2), 2, 3, 4, 4. This yields 1→1→2→3→4→4.

Brute-force approach

Collect all values from both lists into an array, sort the array, then build a new linked list from the sorted values.

Steps

  1. Traverse list1, push all values to an array
  2. Traverse list2, push all values to the same array
  3. Sort the array
  4. Build a new linked list from the sorted array

Time complexity: O((n+m) log(n+m)) · Space complexity: O(n+m)

Trade-offs

  • Uses O(n+m) extra space for the array
  • Sorting takes O((n+m) log(n+m)), slower than necessary
  • Doesn't leverage the fact that both lists are already sorted

Optimal approach

Key insight: Since both lists are sorted, we always pick the smaller head. A dummy node avoids special-casing the first pick.

Use two pointers to compare the heads of both lists and build the merged list by always picking the smaller node.

Steps

  1. Create a dummy node and a 'current' pointer
  2. While both lists are non-empty, compare heads
  3. Attach the smaller head to current.next, advance that list
  4. Advance current to current.next
  5. Attach the remaining non-empty list
  6. Return dummy.next

Time complexity: O(n+m) · Space complexity: O(1)

Pseudocode

function mergeTwoLists(list1, list2):
    dummy = new ListNode(0)
    current = dummy
    
    while list1 is not null AND list2 is not null:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    current.next = list1 OR list2 (whichever is not null)
    return dummy.next

Hints

  • Use a dummy head node so you don't need special logic for the first element
  • Compare the current heads of both lists and attach the smaller one
  • When one list is exhausted, attach the remainder of the other list

Complexity questions

What is the time complexity of collecting all values, sorting, then rebuilding?

O((n+m) log(n+m)). Collecting values is O(n+m), sorting is O((n+m) log(n+m)), and rebuilding is O(n+m). The sort dominates.

What is the space complexity of the brute force approach?

O(n+m). We store all n+m values in an array, requiring O(n+m) extra space.

What is the time complexity of the two-pointer merge approach?

O(n+m). Each comparison advances one pointer. We make at most n+m comparisons total, so it's O(n+m).

What is the space complexity of the two-pointer merge approach?

O(1). We only use a constant number of pointers (dummy, current). We reuse the existing nodes: no new nodes are created.

Check your understanding of Merge Two Sorted Lists

For lists [1,3,5] and [2,4,6], what should the merged result be?

[1,2,3,4,5,6] (sorted merge). The merged list must contain all elements from both lists in sorted (non-decreasing) order: [1,2,3,4,5,6].

If one list is [1,2] and the other is empty, what is the merged result?

[1,2]. Merging any list with an empty list simply returns the non-empty list as-is. The result is [1,2].

For lists [1,4,5] and [1,3,4], how many nodes does the merged list have?

6 (all nodes from both lists). The merged list contains ALL nodes from both lists. Duplicates are kept, not removed. Result: [1,1,3,4,4,5], 6 nodes total.

Related problems

Keep practising