Merge k Sorted Lists

Hard

The problem

You get a list of k linked lists, each sorted from smallest to biggest. Merge them all into one sorted linked list and return its head. If there are no nodes at all, return nil.

Example 1
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
All eight values in sorted order.
Example 2
Input: lists = []
Output: []
There are no lists, so there is nothing to merge.
Example 3
Input: lists = [[], []]
Output: []
Both lists are empty.

Limits

0 ≤ k ≤ 10,000
The total number of nodes is at most 100,000
-10,000 ≤ node value ≤ 10,000
Each list is sorted in non-decreasing order

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

At each step the next output node is the smallest among k heads. What structure finds a minimum fast?

The idea

Min-heap holding the current head of each list; pop the smallest, append, push its next. (Or merge lists pairwise, divide-and-conquer.)

Target: O(N log k) time

Go function shape

func mergeKLists(lists []*ListNode) *ListNode

Reference solution

Tested with go test. Try it yourself first, then compare.

// ListNode is the singly linked list node.
type ListNode struct {
	Val  int
	Next *ListNode
}

type nodeHeap []*ListNode

func (h nodeHeap) Len() int           { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x any)        { *h = append(*h, x.(*ListNode)) }
func (h *nodeHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// MergeKLists: the heap always holds the current head of every list;
// pop the smallest, append it, and push that node's successor.
func MergeKLists(lists []*ListNode) *ListNode {
	h := &nodeHeap{}
	for _, l := range lists {
		if l != nil {
			heap.Push(h, l)
		}
	}
	dummy := &ListNode{}
	tail := dummy
	for h.Len() > 0 {
		n := heap.Pop(h).(*ListNode)
		tail.Next = n
		tail = n
		if n.Next != nil {
			heap.Push(h, n.Next)
		}
	}
	return dummy.Next
}

Read the lesson: Linked List · Fast & Slow Pointers