Merge Two Sorted Lists

Difficulty: Easy

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Example

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: We compare heads of both lists and pick the smaller node each time: 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)