这篇文章给大家介绍golang中怎么合并K个排序链表，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路：
这是一个数组＋链表组合题目，看到链表有序，我们首先想到链表合并子问题
1，这是合并两个有序链表的基础上的扩展
2，简单思路
将依次将第二个起都合并到第一个，复杂度O（k*n）
3，思路二，两两合并，复杂度O（logk*n）
4，注意长度可能是奇数，即使是偶数，两两合并后可能是奇数,需要特殊处理，否则数组越界问题很难处理，很容易死循环
5，扩展思路
用优先队列，每次取最小的元素合并，然后把当前链表下一个元素入队，直到队列为空
代码实现
计算
安全
数据库
网络和加速
企业服务
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func mergeKLists(lists []*ListNode) *ListNode { k:=len(lists) if k==0{ return nil } for k>1{ if k%2==1{ lists[0]=merge(lists[0],lists[k-1]) } k/=2 for i:=0;i<k;i++{ lists[i]=merge(lists[k+i],lists[i]) } } return lists[0]}func merge(l1,l2 *ListNode)*ListNode{ h:=&ListNode{} tmp:=h for l1!=nil && l2!=nil{ if l1.Val<l2.Val{ tmp.Next=l1 l1=l1.Next }else{ tmp.Next=l2 l2=l2.Next } tmp=tmp.Next } if l1!=nil{ tmp.Next=l1 } if l2!=nil{ tmp.Next=l2 } return h.Next}关于golang中怎么合并K个排序链表就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4404121
