移动互联时代网站建设,伪静态规则变动对网站的影响,wordpress发布站点,网站建设公司有多少23. 合并 K 个升序链表 给你一个链表数组#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。 正文
这道题有多种解决方案
堆
比较容易#xff0c;又比较直观的就是堆排序#xff0c;将每个节点加入最小根堆中每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 正文
这道题有多种解决方案
堆
比较容易又比较直观的就是堆排序将每个节点加入最小根堆中依次弹出加入最后的链表就可得出答案事实上并不需要每次都将所有链表加入只需要最开始将每个链表的头节点加入然后在弹出链表时直接将弹出的节点的下一个节点再加入堆即可这样能够有效节省空间。
代码如下
func mergeKLists(lists []*ListNode) *ListNode {lh : ListHeap{}heap.Init(lh)for _, node : range lists {if node ! nil {heap.Push(lh, node)}}dummy : ListNode{}tmp : dummyfor lh.Len() 0 {Node : heap.Pop(lh).(*ListNode)tmp.Next Nodetmp tmp.Nextif Node.Next ! nil {heap.Push(lh, Node.Next)}}return dummy.Next
}type ListHeap []*ListNodefunc (l *ListHeap) Len() int {return len(*l)
}func (l *ListHeap) Less(i, j int) bool {return (*l)[i].Val (*l)[j].Val
}func (l *ListHeap) Swap(i, j int) {(*l)[i], (*l)[j] (*l)[j], (*l)[i]
}func (l *ListHeap) Push(x any) {*l append(*l, x.(*ListNode))
}func (l *ListHeap) Pop() any {res : (*l)[len(*l)-1]*l (*l)[:len(*l)-1]return res
}
堆排序不用ide也太难写了~
分治
跟归并排序的思路类似将链表切片分成两部分分别合并成一个链表再将这两个链表进行合并。
可以理解为 链表1 链表2 链表3 链表4| | | || | | || | | || | | |———————— ————————| |链表 链表——————————————||最终链表代码如下
func mergeKLists(lists []*ListNode) *ListNode {return Merge(lists, 0, len(lists) - 1)
}func Merge(lists []*ListNode, l int, r int) *ListNode {if l r {return lists[l]} else if l r {return nil}mid : (l r) / 2return MergeTwoLists(Merge(lists, l, mid), Merge(lists, mid 1, r))
}func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {dummy : ListNode{}tmp : dummyfor list1 ! nil list2 ! nil {if list1.Val list2.Val {tmp.Next list2tmp tmp.Nextlist2 list2.Next} else {tmp.Next list1tmp tmp.Nextlist1 list1.Next}}if list1 ! nil {tmp.Next list1}if list2 ! nil {tmp.Next list2}return dummy.Next
}
