Merge K Sorted Lists Using Min Heap in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging 3 sorted lists using min heap

What is the printed merged list after running the following Go code that merges 3 sorted linked lists using a min heap?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type ListNode struct {
	Val  int
	Next *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{} {
	n := len(*h)
	item := (*h)[n-1]
	*h = (*h)[:n-1]
	return item
}

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

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

	dummy := &ListNode{}
	current := dummy

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

	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("null")
}

func main() {
	list1 := &ListNode{1, &ListNode{4, &ListNode{5, nil}}}
	list2 := &ListNode{1, &ListNode{3, &ListNode{4, nil}}}
	list3 := &ListNode{2, &ListNode{6, nil}}

	merged := mergeKLists([]*ListNode{list1, list2, list3})
	printList(merged)
}

A 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

C 1 -> 1 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

D 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

💡 Hint

Remember the min heap always pops the smallest current node from all lists.

The min heap merges nodes by always choosing the smallest current node among all lists. The merged list contains all nodes in sorted order: 1,1,2,3,4,4,5,6.

🧠 Conceptual

intermediate

Understanding the role of the min heap in merging K sorted lists

Why is a min heap used to merge K sorted linked lists efficiently?

A Because it merges lists by concatenating them directly

B Because it sorts all elements at once in O(N log N) time

C Because it stores all elements in a balanced binary search tree

D Because it always provides the smallest current element among all lists in O(log K) time

💡 Hint

Think about how to get the smallest element quickly from multiple sorted lists.

A min heap keeps track of the smallest current element from each list, allowing extraction in O(log K) time, making the overall merge efficient.

🔧 Debug

advanced

Identify the error in this min heap implementation for merging lists

What error will occur when running this Go code snippet for merging K sorted lists using a min heap?

DSA Go

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] }

A The merged list will be sorted in descending order, not ascending

B Compilation error due to incorrect method signatures

C Runtime panic due to nil pointer dereference

D The heap will not compile because Less method returns bool incorrectly

💡 Hint

Check the Less method logic and how it affects heap order.

The Less method uses '>' which makes the heap a max heap, so the smallest element is not popped first, resulting in descending order merge.

🚀 Application

advanced

How many nodes are in the merged list after merging these K sorted lists?

Given 4 sorted linked lists with lengths 3, 2, 4, and 1 respectively, how many nodes will the merged list contain after merging using a min heap?

A 10

B 9

C 8

D 11

💡 Hint

Add the lengths of all lists to find total nodes.

The merged list contains all nodes from all lists combined, so total nodes = 3 + 2 + 4 + 1 = 10.

❓ Predict Output

expert

Output of merging empty and non-empty lists using min heap

What is the output of the following Go code that merges 3 lists where one is empty and others have nodes?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type ListNode struct {
	Val  int
	Next *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{} {
	n := len(*h)
	item := (*h)[n-1]
	*h = (*h)[:n-1]
	return item
}

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

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

	dummy := &ListNode{}
	current := dummy

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

	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("null")
}

func main() {
	list1 := (*ListNode)(nil)
	list2 := &ListNode{0, &ListNode{2, nil}}
	list3 := &ListNode{1, nil}

	merged := mergeKLists([]*ListNode{list1, list2, list3})
	printList(merged)
}

A 0 -> 2 -> 1 -> null

B 1 -> 0 -> 2 -> null

C 0 -> 1 -> 2 -> null

D null

💡 Hint

Check how nil lists are skipped and how min heap orders nodes.

The merged list contains nodes 0, 1, and 2 in ascending order: 0 -> 1 -> 2 -> null.