7.4 Merge k Sorted Lists

7.4.1 Problem Metadata

7.4.2 Description

You are given an array of k linked-lists, each sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

7.4.3 Examples

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Input: lists = []
Output: []

7.4.4 Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • All lists are sorted in ascending order

7.4.5 Solution - Min-Heap

7.4.5.1 Walkthrough

This solution uses a min-heap (priority queue) to efficiently select the smallest node across all k lists at each step.

Core Strategy:

  1. Add the head of each non-empty list to the min-heap
  2. Repeatedly extract the minimum node, append it to the result
  3. If the extracted node has a next, add it to the heap
  4. Continue until the heap is empty

Why Min-Heap? With k lists, a naive comparison would take O(k) per node. A min-heap reduces this to O(log k), making the overall time O(n log k) instead of O(nk).

Example: Merge [[1,4,5],[1,3,4],[2,6]]:

Initial heap: [1, 1, 2] (heads of each list)
Extract 1 → add to result, push 4 → heap: [1, 2, 4]
Extract 1 → add to result, push 3 → heap: [2, 3, 4]
Extract 2 → add to result, push 6 → heap: [3, 4, 6]
Extract 3 → add to result, push 4 → heap: [4, 4, 6]
...continue until heap empty
Result: [1,1,2,3,4,4,5,6]

7.4.5.2 Analysis

  • Time Complexity: O(n log k) - Each of n nodes is added/removed from heap once, heap operations are O(log k)
  • Space Complexity: O(k) - Heap contains at most k nodes at any time

7.4.5.3 Implementation Steps

  1. Create a min-heap ordered by node value.
  2. Add the head of each non-empty list to the heap.
  3. While heap is not empty, extract min, append to result, push next if exists.
  4. Return dummy.next.

7.4.5.4 Code - Java

public ListNode mergeKLists(ListNode[] lists) {
    //Add the head of each non-empty list to the min-heap
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    /*
     *  Repeatedly extract the minimum node from min-heap, append it to the result list
     *  If the extracted node has a next, add it to the min-heap
     *  Continue until the min-heap is empty        
     */
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) {
            pq.offer(node.next);
        }
    }
    return dummy.next;
}

7.4.5.5 Code - Golang

Go requires implementing the heap.Interface for custom types. See Heap Implementation for detailed explanation of the heap interface and how container/heap works.

import "container/heap"

func mergeKLists(lists []*ListNode) *ListNode {
    // Create and initialize min-heap
    h := &MinHeap{}
    heap.Init(h)

    // Add the head of each non-empty list to the min-heap
    for _, node := range lists {
        if node != nil {
            heap.Push(h, node)
        }
    }

    dummy := &ListNode{}
    tail := dummy

    // Repeatedly extract the minimum node from min-heap, append it to the result
    // If the extracted node has a next, add it to the min-heap
    // Continue until the min-heap is empty
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        tail.Next = node
        tail = tail.Next
        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }

    return dummy.Next
}

// MinHeap implements heap.Interface for *ListNode
type MinHeap []*ListNode

func (h MinHeap) Len() int {
    return len(h)
}

func (h MinHeap) Less(i, j int) bool {
    return h[i].Val < h[j].Val
}

func (h MinHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}