golang中怎么合并K个排序链表
这篇文章给大家介绍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 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 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个排序链表就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
文章标题：golang中怎么合并K个排序链表
本文路径：
http://kswjz.com/article/pidhcc.html
扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
