Go语言每日一练——链表篇(五)

传送门

牛客面试笔试必刷101题 ----------------合并k个已排序的链表

题目以及解析

题目

解题代码及解析

解析

这一道题与昨天的合并链表题目类似，但是由于有K个且时间复杂度要求控制在O(nlogn)，这里主要有两种解法：一种是依旧使用归并来合并，一种则是利用堆这种数据结构来实现。

代码

方法一：堆(优先队列)

package main
import _"fmt"
import . "nc_tools"
import "container/heap"/** type ListNode struct{*   Val int*   Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param lists ListNode类一维数组 * @return ListNode类
*/
func mergeKLists( lists []*ListNode ) *ListNode {p:=hp{}for _,head:=range lists{if head!=nil{p=append(p,head)}}heap.Init(&p)//初始化堆curr:=&ListNode{}dump:=currfor len(p)>0{node:=heap.Pop(&p).(*ListNode)if node.Next!=nil{heap.Push(&p,node.Next)}curr.Next=nodecurr=curr.Next}return dump.Next
}//定义小根堆
type hp []*ListNodefunc (p hp) Len() int{return len(p)
}
func (p hp)Less(i,j int) bool{  //通过该函数来确定小根堆还是大根堆return p[i].Val<p[j].Val
}func (p hp)Swap(i,j int){p[i],p[j]=p[j],p[i]
}func (p *hp)Push(value interface{}){*p=append(*p,value.(*ListNode))
}func (p *hp)Pop() any{a:=*pvalue:=a[len(a)-1]*p=a[:len(a)-1]return value
}

方法二：分治

package mainimport (_ "container/list"_ "fmt". "nc_tools"_ "net"
)/** type ListNode struct{*   Val int*   Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param lists ListNode类一维数组* @return ListNode类*/
func Merge(list1 *ListNode, list2 *ListNode) *ListNode {dump := &ListNode{}current := dumpfor list1 != nil && list2 != nil {if list1.Val < list2.Val {current.Next = list1list1 = list1.Next} else {current.Next = list2list2 = list2.Next}current=current.Next}if list1 != nil {current.Next = list1list1 = list1.Next}if list2 != nil {current.Next = list2list2 = list2.Next}current = current.Nextreturn dump.Next
}func mergeKLists(lists []*ListNode) *ListNode {m := len(lists)if m == 0 {return nil}if m == 1 {return lists[0]}left := mergeKLists(lists[:m/2])right := mergeKLists(lists[m/2:])return Merge(left, right)
}

总结：

这题依旧是一道合并链表题，但是简单的遍历来挨个合并会使时间复杂度上升到O(n^2),所以需要采取一些巧劲来实现，但是玩具的最好的还是使用堆来解题，可以更好了解到堆泛型在Go语言中如何去使用。