23. 合并 K 个升序链表

### 题目

[合并 k 个有序链表](https://leetcode.cn/problems/merge-k-sorted-lists/ "合并 k 个有序链表")

### 思路

1. 合并K个链表，本质上和合并两个链表的逻辑相似，都是不断拼接多个链表中的最小结点，拼接成新链表
2. 关键在于如何快速找到N个链表中的最小结点

### 暴力解

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    p := dummy

for {
        min := math.MaxInt
        minIdx := 0
        for idx := range lists {
            if lists[idx] == nil {
                continue
            }
            if lists[idx].Val < min {
                min = lists[idx].Val
                minIdx = idx
            }
        }

if min == math.MaxInt {
            break
        }
        p.Next = lists[minIdx]
        p = p.Next
        lists[minIdx] = lists[minIdx].Next
    }

return dummy.Next
}
```

### 优先级队列（二叉堆）

把链表节点放入一个最小堆，就可以每次获得k个节点中的最小节点

go中可以实现heap.Interface来构建优先级队列

```go

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

```

算法实现：

```go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    p := dummy

mh := minHeaps{}

for _, item := range lists {
        if item != nil {
            mh = append(mh, item)
        }
    }

heap.Init(&mh)

for len(mh) > 0 {
        x := heap.Pop(&mh).(*ListNode)
        p.Next = x
        if x.Next != nil {
            heap.Push(&mh, x.Next)
        }
        p = p.Next
    }

return dummy.Next
}

type minHeaps []*ListNode

func (h *minHeaps) Len() int {
    return len(*h)
}

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

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

func (h *minHeaps) Push(x any) {
    (*h) = append((*h), x.(*ListNode))
}

func (h *minHeaps) Pop() any {
    last := len(*h) - 1
    if last < 0 {
        return nil
    }
    x := (*h)[last]
    (*h) = (*h)[:last]
    return x
}

```