阿坝州网站建设公司

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://azwzsj.com/article/pidhcc.html

其他资讯