当前位置：首页 > 编程日记 > 正文

刻意练习：LeetCode实战 -- Task12. 合并K个排序链表

编程日记 2024-09-26 06:30:00

背景

本篇图文是LSGO软件技术团队组织的第二期基础算法（Leetcode）刻意练习训练营的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了三个简单、两个中等、一个困难等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：链表

链表（Linked List） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里除了存放本身数据（data fields）之外还存放其后继节点的指针（Pointer）。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[1->4->5,1->3->4,2->6
]
输出: 1->1->2->3->4->4->5->6

实现

第一种：两两合并的方式

构造合并两个有序链表得到一个新的有序链表的方法：ListNode MergeTwoLists(ListNode l1, ListNode l2)。可以使用该方法合并前两个有序链表得到一个新的有序链表，之后把这个新链表与第三个有序链表合并，依次类推，最后得到合并K个有序列表的新列表。

执行结果：通过
执行用时：256 ms, 在所有 C# 提交中击败了 36.69% 的用户
内存消耗：29.3 MB, 在所有 C# 提交中击败了 18.37% 的用户

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution 
{public ListNode MergeTwoLists(ListNode l1, ListNode l2) {ListNode pHead = new ListNode(int.MaxValue);ListNode temp = pHead;while (l1 != null && l2 != null){if (l1.val < l2.val){temp.next = l1;l1 = l1.next;}else{temp.next = l2;l2 = l2.next;}temp = temp.next;}if (l1 != null)temp.next = l1;if (l2 != null)temp.next = l2;return pHead.next;}public ListNode MergeKLists(ListNode[] lists) {if (lists.Length == 0)return null;ListNode result = lists[0];for (int i = 1; i < lists.Length; i++){result = MergeTwoLists(result, lists[i]);}return result;}
}

第二种：选择值最小结点的方式

执行结果：通过
执行用时：776 ms, 在所有 C# 提交中击败了 7.10% 的用户
内存消耗：29.2 MB, 在所有 C# 提交中击败了 22.45% 的用户

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution 
{public ListNode MergeKLists(ListNode[] lists) {int len = lists.Length;if (len == 0)return null;ListNode pHead = new ListNode(-1);ListNode temp = pHead;while (true){int min = int.MaxValue;int minIndex = -1;for (int i = 0; i < len; i++){if (lists[i] != null){if (lists[i].val < min){minIndex = i;min = lists[i].val;}}}if (minIndex == -1){break;}temp.next = lists[minIndex];temp = temp.next;lists[minIndex] = lists[minIndex].next;}return pHead.next;        }
}

来源

https://leetcode-cn.com/problems/merge-k-sorted-lists/

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20379.html

刻意练习：LeetCode实战 -- Task12. 合并K个排序链表

背景

题目

实现

相关文章：

软测培训机构哪个比较好

刻意练习：LeetCode实战 -- Task13. 罗马数字转整数

[翻译]ASP.NET MVC 3 开发的20个秘诀（十二）[20 Recipes for Programming MVC 3]：缩放图片尺寸创建缩略图...

Vue.js双向绑定的实现原理

学习UI设计的一些小技巧你会了吗

30个精美的模板，贺卡，图形圣诞素材

刻意练习：LeetCode实战 -- Task14. 最长公共前缀

6.1.1 验证注解的使用

Javascript创建数组的方式你了解了吗

loadrunner另类玩法【测试帮日记公开课】

刻意练习：LeetCode实战 -- Task15. 有效的括号

对口令协议的几种攻击方式

初学者如何学Java开发

[算法] [常微分方程] [欧拉法改进欧拉法经典R-K算法]

刻意练习：LeetCode实战 -- Task16. 无重复字符的最长子串

轻松实现QQ用户接入

web前端培训之Javascript如何改变数组的长度?

刻意练习：LeetCode实战 -- Task17. 最长回文子串

CvBlobTrackerCC 多目标跟踪算法简析

linux基础学习（二）

ui设计培训需要什么基础?如何入门学习?

SQL Server日志清除的两种方法 .

刻意练习：LeetCode实战 -- Task18. 正则表达式匹配

CentOS7启动图形界面

Java培训学习步骤有哪些

extjs 4 tab panel得strip在IE下右偏解决办法

Vbox共享文件夹不显示了

刻意练习：LeetCode实战 -- Task19. 相同的树

找Java培训机构需要注意那些

字符串的最大相似匹配