Merge K Sorted Lists

You are given an array of k linked lists, where each linked list is sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

Function signature

func MergeKLists(lists []*ListNode) *ListNode

ListNode definition

type ListNode struct {
    Val  int
    Next *ListNode
}

Examples

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation:
  List 1: 1 -> 4 -> 5
  List 2: 1 -> 3 -> 4
  List 3: 2 -> 6
  Merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2:

Input: lists = []
Output: nil

Example 3:

Input: lists = [[]]
Output: nil

Example 4:

Input: lists = [[1],[2],[3]]
Output: [1,2,3]

Constraints

• k == len(lists)
• 0 <= k <= 10000
• 0 <= len(lists[i]) <= 500
• -10000 <= lists[i][j] <= 10000
• Each list is sorted in ascending order

Hints

1. The naive approach merges lists one by one. What's the time complexity?
2. A min-heap can efficiently track the smallest element across all lists.
3. Push the head of each list to the heap. Pop the minimum, add it to the result, and push its next node.

Notes

• Time: O(n log k) where n = total elements, k = number of lists.
• This is a classic multi-way merge problem, also used in external sorting.