合并K个升序链表

合并K个升序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/

最小堆

把所有链表的头节点放入最小堆，每次从中取出最小的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    h := new(minHeap)
    for i := 0; i < len(lists); i++ {
        if lists[i] != nil {
            heap.Push(h, lists[i])
        }
    }

    head := new(ListNode)
    curr := head

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

    return head.Next
}

// 最小堆实现
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{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

最小堆的实现参考：