NUHMAN.com

Introduction

LeetCode 23: Merge k Sorted Lists is a highly rated problem that asks you to merge k sorted linked lists into a single sorted list. The challenge is to do it efficiently, especially when k is large.

This problem builds on the ideas of merging two lists (like LeetCode 21), but at scale. The optimal solution uses a min-heap to always select the smallest current node from the k heads.

Problem Statement

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

Examples

go

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

Input: lists = []
Output: []
go

Input: lists = [[]]
Output: []

Approach: Min-Heap (Priority Queue)

The idea is to push the head of each list into a min-heap. The heap helps us get the smallest current node among all lists in O(log k) time.

Steps:

1. Initialize a min-heap and insert the first node of each list.
2. While the heap is not empty:

• Pop the smallest node and append it to the result list.
• If that node has a next, push it into the heap.

1. Return the merged list.

Go Implementation

Go doesn't have a built-in priority queue, but we can implement it using the container/heap package.

Heap Setup

go

package main

import (
    "container/heap"
    "fmt"
)

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// Priority Queue
type ListNodeHeap []*ListNode

func (h ListNodeHeap) Len() int           { return len(h) }
func (h ListNodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h ListNodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

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

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

Merge Function

go

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &ListNodeHeap{}
    heap.Init(minHeap)

    for _, l := range lists {
        if l != nil {
            heap.Push(minHeap, l)
        }
    }

    dummy := &ListNode{}
    current := dummy

    for minHeap.Len() > 0 {
        smallest := heap.Pop(minHeap).(*ListNode)
        current.Next = smallest
        current = current.Next
        if smallest.Next != nil {
            heap.Push(minHeap, smallest.Next)
        }
    }

    return dummy.Next
}

Helper Functions for Testing

go

func createList(nums []int) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    for _, val := range nums {
        curr.Next = &ListNode{Val: val}
        curr = curr.Next
    }
    return dummy.Next
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

func main() {
    lists := []*ListNode{
        createList([]int{1, 4, 5}),
        createList([]int{1, 3, 4}),
        createList([]int{2, 6}),
    }

    result := mergeKLists(lists)
    fmt.Print("Merged List: ")
    printList(result)
}

Time and Space Complexity

• Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
• Space Complexity: O(k) for the heap.

Alternative Approach: Divide and Conquer

You can also merge lists in pairs (like merge sort) to reduce the problem from k lists to 1. This approach has similar complexity but less heap overhead.

Key Takeaways

• This is a classic heap + linked list problem.
• Use Go’s container/heap for efficient minimum selection.
• Understand how to build and use custom types in Go to solve real-world problems like merging sorted streams.