中国东凤网站制作,佛山市做网站的,wordpress 页面模板 自定义,免费自助建网站题目链接#xff1a;23. 合并 K 个升序链表 题目描述#xff1a; 数据范围#xff1a;
**思考#xff1a;**这题实际上就是合并两个有序列表的进阶版#xff0c;只不过这里变成了合并K个#xff0c;那么这里我们显然就知道#xff0c;核心的合并两个有序列表的思路不…题目链接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 : (lr)1return mergeTwoLists(merge(l,mid,lists),merge(mid1,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。
