【LeetCode】23. 合并 K 个升序链表

题目链接：23. 合并 K 个升序链表
题目描述：

数据范围：

**思考：**这题实际上就是合并两个有序列表的进阶版，只不过这里变成了合并K个，那么这里我们显然就知道，核心的合并两个有序列表的思路不变，剩下的重点处理就在于如何将这K个链表进行两两合并了，方式有很多，但效率不一，下面介绍几种易想到的思路：

方法一：顺序合并

顺序合并思路很简单，就是顺序地将这K个链表两两地进行合并。

代码：

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return new(ListNode).Next}res := lists[0]lists = lists[1:]for _,list := range lists {res = mergeTwoLists(res,list)}return res
}
// 合并两个升序链表
func mergeTwoLists(l1 ,l2 *ListNode) *ListNode {head := new(ListNode)l := headfor ;l1 != nil && l2 != nil; {if l1.Val < l2.Val {l.Next = l1l1 = l1.Next}else {l.Next = l2l2 = l2.Next}l = l.Next}if l1 != nil {l.Next = l1}if l2 != nil {l.Next = l2}return head.Next
}

方法二、分治

顺序合并的效率并不高，这样做就类似于阻塞操作，合并前面的链表的时候，无关的链表啥事儿都干不了，因此，我们可以考虑进行分治，先递归地划分区间两两合并，最后再将总的合并起来。

代码：

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return new(ListNode).Next}return merge(0,len(lists)-1,lists)
}func merge(l,r int,lists []*ListNode) *ListNode {if l > r {return nil}if l == r {return lists[l]}mid := (l+r)>>1return mergeTwoLists(merge(l,mid,lists),merge(mid+1,r,lists))
}func mergeTwoLists(l1 ,l2 *ListNode) *ListNode {head := new(ListNode)l := headfor ;l1 != nil && l2 != nil; {if l1.Val < l2.Val {l.Next = l1l1 = l1.Next}else {l.Next = l2l2 = l2.Next}l = l.Next}if l1 != nil {l.Next = l1}if l2 != nil {l.Next = l2}return head.Next
}

方法三、小根堆

看了下题解找出了不同的写法的，基本上用了小根堆(优先队列)的结构来实现的，思路就是初始时将每个链表的头结点加入到堆中，调整成为一个小根堆，那么堆顶结点一定是最小的。循环取堆中的元素，直到堆为空，注意，每次从堆中取出一个节点就需要将该节点从堆中移除，并将这个节点的下一个节点加入到堆中。

代码：

func mergeKLists(lists []*ListNode) *ListNode {h := hp{}for _, head := range lists {if head != nil {h = append(h, head)}}heap.Init(&h) // 初始化小根堆res := &ListNode{} // 哨兵节点，作为合并后链表头节点的前一个节点cur := res // 当前合并的链表位置，也就res链表末尾for len(h) > 0 {node := heap.Pop(&h).(*ListNode) // 取出堆顶元素if node.Next != nil { // 该节点的下一个节点不空，就再加入堆中heap.Push(&h, node.Next)}cur.Next = node // 记录到答案中cur = cur.Next // 准备合并下一个节点}return res.Next
}// golang中小根堆的实现
type hp []*ListNode
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) {*h = append(*h, x.(*ListNode))}
func (h *hp) Pop() interface{} {n := len(*h)ans := (*h)[n-1] // n-1个元素就是堆顶元素*h = (*h)[:n-1]return ans
}

这种做法很容易能看出复杂度为O(n*logk)，其中k是链表长度，而n是所有链表节点数之和，这里logk主要是k个链表加入到堆中，所以时间复杂度为logk。