Coding Interview PatternsMerge Two Sorted Lists
EasyK-way Merge

Merge Two Sorted Lists

Explanation & Solution

Practice Problem

Description

Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list by splicing together nodes from both lists.

Return the head of the merged linked list.

Input:l1 = [1,2,4], l2 = [1,3,4]
0
1
1
2
2
4
0
1
1
3
2
4
Output:[1,1,2,3,4,4]
0
1
1
1
2
2
3
3
4
4
5
4

Explanation: Merging [1→2→4] and [1→3→4] produces [1→1→2→3→4→4].

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Approach

K-way Merge pattern

1. Create a Dummy Head

  • Allocate a sentinel dummy node so we never have to handle the empty-result edge case specially
  • curr starts at dummy and advances as we build the merged list

2. Compare and Link the Smaller Node

  • While both l1 and l2 are non-null, compare their .val
  • Set curr.next to whichever is smaller and advance that list pointer
  • Advance curr forward one step

3. Append the Remaining Tail

  • Once one list is exhausted, the other may still have nodes
  • Set curr.next = l1 || l2 to attach the entire remaining tail in O(1)

4. Return the Merged Head

  • Return dummy.next — the sentinel node itself is discarded

Key Insight

  • The dummy head trick eliminates special-casing for an initially empty result list
Time
O(m + n)each node is visited exactly once
Space
O(1)we reuse existing nodes; only the dummy head is extra

Solution Code

Next
Merge Sorted Array