Merge k Sorted Lists

hard

Merge k sorted linked lists into one sorted linked list using divide and conquer

Merge K Sorted Lists

Key Insight

Divide-and-conquer: merge pairs of lists, halving the count each round

Step 1Initial K=3 Lists
List 0: [1,4,5]List 1: [1,3,4]List 2: [2,6]
1
4
5
null
List 2
1
3
4
null
New nodes
2
6

Three sorted lists: [1,4,5], [1,3,4], and [2,6].

1 / 5

Learn the Pattern

HeapUse a heap (priority queue) when you repeatedly need the minimum or maximum of a changing set while also inserting and deleting values efficiently.
Practice the Code

Step-by-Step Walkthrough: Merge K Sorted Lists

Divide-and-conquer: merge pairs of lists, halving the count each round

  1. Initial K=3 Lists

    Three sorted lists: [1,4,5], [1,3,4], and [2,6].

  2. Round 1: Merge Lists 0 + 1

    Merge [1,4,5] and [1,3,4] using standard two-list merge.

  3. Round 1 Result

    Lists 0+1 merged into [1,1,3,4,4,5]. List 2 [2,6] waits for next round.

  4. Round 2: Merge Result + List 2

    Merge [1,1,3,4,4,5] with [2,6] to produce the final sorted list.

  5. Result

    All three lists merged into one sorted list.