当前位置： 首页 > news >正文

江阴早晨网站建设电脑培训学校网站

news 2025/7/1 12:53:14
江阴早晨网站建设,电脑培训学校网站,网站建设费用计入哪个科目,ec网站域名1. 题目 描述 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围&#xff1a;节点总数满足 0≤n≤105&#xff0c;链表个数满足 1≤k≤105 &#xff0c;每个链表的长度满足 1≤len≤200 &#xff0c;每个节点的值满足∣val∣<1000 要求&#xff1a…

1. 题目

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数满足 0≤n≤105，链表个数满足 1≤k≤105 ，每个链表的长度满足 1≤len≤200 ，每个节点的值满足∣val∣<=1000

要求：时间复杂度 O(nlogk)

示例1

输入：

[{1,2,3},{4,5,6,7}]

返回值：

{1,2,3,4,5,6,7}

示例2

输入：

[{1,2},{1,4,5},{6}]

返回值：

{1,1,2,4,5,6}

2. 解题思路

根据题目要求，时间复杂度 O(nlogk)。如果K个升序的链表如果执行两两合并，时间复杂度（n*k^2）不满足要求。这时我们可以借助于堆（复杂度为nlogk）来完成K个链表的排序。

假如链表分别为：1→2、 1→4→5与6，合并之后为：1→1→2→4→5→6，结构如下图所示：

具体思路如下：

第一步： 定义（引用）小顶堆。

小顶堆的最小值存储于堆顶，可以完成从小到大的排序操作。

第二步：每个链表的第一个节点放入堆中。

链表的第一个节点加入到堆中之后，堆会根据链表节点的值进行堆化，将节点值最小的放到堆顶，如下图所示。

第三步：从堆中取出元素（取出的元素为节点值最小的），构成新的链表。

接下来从堆中取出堆顶的节点，并将此节点追加到新链表的末尾。节点出堆之后，它对应链表的下一个节点加入到堆中（条件是：即将加入的节点不为Null）。

从堆中取出堆顶的节点1，将它追加到新链表中去，同时1的后一个节点2入堆，加入堆之后，堆会自己进行堆化，将链表节点值最小的重新放置到堆顶。如下图所示：

之后，再从堆中取出堆顶元素1，将其追加到新链表的末尾，1的后一个节点4入堆，堆再自行进行堆化，堆顶始终保存的是节点值最小的节点，如下图所示：

一直按照此方法来操作，如果一个节点出堆，它的下一个节点为Null，则Null不入堆。这样一来最终堆中的所有节点都会被取完，如下图所示：

第四步：返回新链表的头节点。

如果堆已经空了，这时返回虚拟头结点tmpHead的下一个节点即可。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

  • Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370261

  • Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1366717

  • Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364394

3. 编码实现

3.1 Python编码实现

from typing import List
from queue import PriorityQueueclass ListNode:def __init__(self, x):self.val = x  # 链表的数值域self.next = None  # 链表的指针域# 从链表节点尾部添加节点
def insert_node(node, value):if node is None:print("node is None")return# 创建一个新节点new_node = ListNode(value)cur = node# 找到链表的末尾节点while cur.next is not None:cur = cur.next# 末尾节点的next指针域连接新节点cur.next = new_node# 打印链表（从链表头结点开始打印链表的值）
def print_node(node):cur = node# 遍历每一个节点while cur is not None:print(cur.val, end="\t")cur = cur.next  # 更改指针变量的指向print()#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
class Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:# write code here# 1. 定义（引用）小顶堆heap = PriorityQueue()# 2. 每个链表的第一个节点放入堆中for i in range(len(lists)):# 不为空则加入小顶堆if lists[i] is not None:heap.put((lists[i].val, i))  # 注意:加入的是元组（优先级,值）lists[i] = lists[i].next  # 移动指针变量，lists[i]执行下一个节点# 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表tmp_head = ListNode(-1)cur = tmp_head# 从堆中取元素（节点），直到小顶堆为空while not heap.empty():# 取出最小的元素val, idx = heap.get()  # 注意:取出来的值也是元组，即优先级、值（优先级的值越小（优先级越高），越先取出来）# 节点连接cur.next = ListNode(val)cur = cur.nextif lists[idx] is not None:# 取出（元素）节点的下一个节点值添加到堆中heap.put((lists[idx].val, idx))lists[idx] = lists[idx].next  # lists[i]保存下一个节点# 4. 返回新链表的头节点return tmp_head.nextif __name__ == '__main__':list1 = ListNode(1)list1.next = ListNode(2)print_node(list1)list2 = ListNode(1)list2.next = ListNode(4)list2.next.next = ListNode(5)print_node(list2)list3 = ListNode(6)print_node(list3)old_list = [list1, list2, list3]s = Solution()new_list = s.mergeKLists(old_list)print_node(new_list)

3.2 Java编码实现

package LL05;import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;public class Main {//定义链表节点static class ListNode {private int val;  //链表的数值域private ListNode next; //链表的指针域public ListNode(int data) {this.val = data;this.next = null;}}//添加链表节点private static void insertNode(ListNode node, int data) {if (node == null) {return;}//创建一个新节点ListNode newNode = new ListNode(data);ListNode cur = node;//找到链表的末尾节点while (cur.next != null) {cur = cur.next;}//末尾节点的next指针域连接新节点cur.next = newNode;}//打印链表（从头节点开始打印链表的每一个节点）private static void printNode(ListNode node) {ListNode cur = node;//遍历每一个节点while (cur != null) {System.out.print(cur.val + "\t");cur = cur.next; //更改指针变量的指向}System.out.println();}public static class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param lists ListNode类ArrayList* @return ListNode类*/public ListNode mergeKLists (ArrayList<ListNode> lists) {// write code here// 1. 定义（引用）小顶堆Queue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {//默认：小顶堆return o1.val - o2.val;}});// 2. 每个链表的第一个节点放入堆中//遍历所有链表第一个元素for (int i = 0; i < lists.size(); i++) {//不为空则加入小顶堆if (lists.get(i) != null) {heap.add(lists.get(i));}}// 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表ListNode tmpHead = new ListNode(-1);ListNode cur = tmpHead;//从堆中取元素（节点），直到小顶堆为空while (!heap.isEmpty()) {//取出最小的元素ListNode tmp = heap.poll();//节点连接cur.next = tmp;cur = cur.next;//取出（元素）节点的下一个节点添加到堆中if (tmp.next != null) {heap.add(tmp.next);}}// 4. 返回新链表的头节点return tmpHead.next;}}public static void main(String[] args) {ListNode list1 = new ListNode(1);list1.next = new ListNode(2);printNode(list1);ListNode list2 = new ListNode(1);list2.next = new ListNode(4);list2.next.next = new ListNode(5);printNode(list2);ListNode list3 = new ListNode(6);printNode(list3);ArrayList<ListNode> lists = new ArrayList<>();lists.add(list1);lists.add(list2);lists.add(list3);Solution solution = new Solution();ListNode newList = solution.mergeKLists(lists);printNode(newList);}
}

3.3 Golang编码实现

package mainimport ("container/heap""fmt"
)// ListNode 定义链表节点
type ListNode struct {Val  int       //链表的数值域Next *ListNode //链表的指针域
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param lists ListNode类一维数组* @return ListNode类*/
func mergeKLists(lists []*ListNode) *ListNode {// write code here// 1. 定义（引用）小顶堆myHeap := &MyHeap{}heap.Init(myHeap)// 2. 每个链表的第一个节点放入堆中//遍历所有链表第一个元素for i := 0; i < len(lists); i++ {//不为空则加入小顶堆if lists[i] != nil {heap.Push(myHeap, lists[i])}}// 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表tmpHead := &ListNode{Val: -1}cur := tmpHead//从堆中取元素（节点），直到小顶堆为空for myHeap.Len() > 0 {//取出最小的元素tmp := heap.Pop(myHeap).(*ListNode)//节点连接cur.Next = tmpcur = cur.Next//取出（元素）节点的下一个节点添加到堆中if tmp.Next != nil {heap.Push(myHeap, tmp.Next)}}// 4. 返回新链表的头节点return tmpHead.Next}type MyHeap []*ListNodefunc (h MyHeap) Len() int {return len(h)
}
func (h MyHeap) Less(i, j int) bool {//小顶堆return h[i].Val < h[j].Val
}
func (h MyHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]}
func (h *MyHeap) Push(v interface{}) {*h = append(*h, v.(*ListNode))
}
func (h *MyHeap) Pop() interface{} {old := *hn := len(old)v := old[n-1]*h = old[0 : n-1]return v
}
func main() {list1 := &ListNode{Val: 1}list1.Next = &ListNode{Val: 2}list1.Print()list2 := &ListNode{Val: 1}list2.Next = &ListNode{Val: 4}list2.Next.Next = &ListNode{Val: 5}list2.Print()list3 := &ListNode{Val: 6}list3.Print()lists := []*ListNode{list1, list2, list3}newList := mergeKLists(lists)newList.Print()
}// Insert 从链表节点尾部添加节点
func (ln *ListNode) Insert(val int) {if ln == nil {return}//创建一个新节点newNode := &ListNode{Val: val}cur := ln//找到链表的末尾节点for cur.Next != nil {cur = cur.Next}//末尾节点的next指针域连接新节点cur.Next = newNode
}// Print 从链表头结点开始打印链表的值
func (ln *ListNode) Print() {if ln == nil {return}cur := ln//遍历每一个节点for cur != nil {fmt.Print(cur.Val, "\t")cur = cur.Next //更改指针变量的指向}fmt.Println()
}//TODO： golang heap的使用：https://golang.google.cn/pkg/container/heap/

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解。

  • Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370261

  • Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1366717

  • Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364394

4.小结

本题可以通过小顶堆完成，具体步骤为：

  • 定义（引用）小顶堆；

  • 每个链表的第一个节点放入堆中；

  • 从堆中取出元素（取出的元素为节点值最小的），构成新的链表；

  • 返回新链表的头节点。

难点在于小顶堆的应用。

更多算法视频讲解，你可以从以下地址找到：

  • Python编码实现：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1509965

  • Java编码实现：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1510007

  • Golang编码实现：数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1509945

对于链表的相关操作，我们总结了一套【可视化+图解】方法，依据此方法来解决链表相关问题，链表操作变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：山重水复疑无路，柳暗花明又一村。

http://www.cadmedia.cn/news/14393.html

相关文章：

  • 遵义会议在线网站优化排名软件
  • 如何做微信网站建设桔子seo工具
  • 泉州建站软件新手怎么引流推广推广引流
  • 东北网站建设百度网址大全旧版
  • 建设网站的基本流程是什么sem工作原理
  • 中国建设银行官网下载中心seo网站免费优化软件
  • 制作微网站公司搜狗网址导航
  • 电子商务网站建设方乔拓云智能建站官网
  • net112企业建站系统最好的搜索引擎
  • 免费b站在线观看人数在哪里制作一个网站步骤
  • 陇城科技网站建设长沙靠谱seo优化价格
  • 网站建设 教学视频想要导航推广网页怎么做
  • 黑龙江龙采做网站如何国内营销推广渠道
  • 阿里云Ubuntu安装WordPressseo一键优化
  • 网站建设 qq业务网制作百度软件下载中心官方网站
  • 海口网站建设fwlit广州google推广
  • 网站规划建设与管理维护论文一件代发48个货源网站
  • 乌鲁木齐企业网站建设公司做销售最挣钱的10个行业
  • 做网站怎么选云主机廊坊seo排名公司
  • 怎么打开手机app学校seo推广培训班
  • 重庆梁平网站建设公司简阳seo排名优化课程
  • 最权威的做网站的公司哪家好营销型网站制作成都
  • 长沙仿站模板网站建设交换链接的其它叫法是
  • 学校网站 建设 价格2021时事政治热点50条
  • 深圳推广公司哪家最好单页网站怎么优化
  • 美轮美奂的网站建设电脑优化大师官方免费下载
  • 江苏首天建设集团网站企业站seo案例分析
  • 贵州网络公司网站建设数据分析师就业前景
  • 济南建设集团网站网站推广方法大全
  • 运城网站建设公司有多少手机百度旧版本下载