LeetCode实战：合并K个排序链表

题目英文

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
 1->4->5,
 1->3->4,
 2->6
]
Output: 1->1->2->3->4->4->5->6

题目中文

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

示例:

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

算法实现

第一种方式：每次选择值最小的节点插入到链表中。

/**
 * 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(int.MaxValue);
 ListNode temp = pHead;
 while (true)
 {
 bool isBreak = true;
 int min = int.MaxValue;
 int minIndex = 0;
 for (int i = 0; i < len; i++)
 {
 if (lists[i] != null)
 {
 if (lists[i].val < min)
 {
 minIndex = i;
 min = lists[i].val;
 }
 isBreak = false;
 }
 }
 if (isBreak)
 {
 break;
 }
 temp.next = lists[minIndex];
 temp = temp.next;
 lists[minIndex] = lists[minIndex].next;
 }
 temp.next = null;
 return pHead.next; 
 }
}

第二种方式

：利用 合并两个有序链表 的方法。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * public int val;
 * public ListNode next;
 * public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
 public static 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;
 }
}

实验结果

第一种方式的提交结果：

• 状态：通过
• 131 / 131 个通过测试用例
• 执行用时：772 ms

提交结果

第二种方式的提交结果：

• 状态：通过
• 131 / 131 个通过测试用例
• 执行用时：332 ms

提交结果

相关图文：

• LeetCode实战：两数之和
• LeetCode实战：求众数
• LeetCode实战：快乐数
• LeetCode实战：删除链表的倒数第N个节点
• LeetCode实战：合并两个有序链表
• LeetCode实战：两两交换链表中的节点
• LeetCode实战：旋转链表
• LeetCode实战：相同的树
• LeetCode实战：对称二叉树
• LeetCode实战：二叉树的最大深度
• LeetCode实战：搜索二维矩阵
• LeetCode实战：将有序数组转换为二叉搜索树

经过8年多的发展，LSGO软件技术团队在「地理信息系统」、「数据统计分析」、「计算机视觉」等领域积累了丰富的研发经验，也建立了人才培养的完备体系，由于自己准备在「量化交易」领域精进技能，如果大家对这个领域感兴趣可以与我联系，加入我们的量化学习群一起学习探讨。

在这个领域我已做了以下积累：

策略部分：

• 数字货币 One 的投资价值分析
• 数字资产量化中的跨市场套利策略
• 数字资产量化中的同市场套利策略
• 数字资产量化中的网格交易法
• 我们能否效仿李笑来的投资策略？
• 赚钱是刚需，如何正确的交易股票？

数据部分：

• 如何利用 C# 爬取 One 的交易数据？
• 如何利用 C# 爬取 One 持有者返利数据？
• 如何利用 C# 爬取BigOne交易所的公告？
• 如何利用 C# 爬取Gate.io交易所的公告？
• 如何利用 C# 爬取「财报说」中的股票数据？

自动化交易部分：

• 封装BigOne API：身份验证
• 封装BigOne API：获取账户资产
• 封装BigOne API：订单系统
• 封装BigOne API：网格交易法
• 封装BigOne API：代码的重构
• 进一步完善自动化交易系统 01
• 进一步完善自动化交易系统 02
• 进一步完善自动化交易系统 03
• 进一步完善自动化交易系统 04
• 如何开发「股票数据分析软件」（上）
• 如何开发「股票数据分析软件」（中）
• 如何开发「股票数据分析软件」（下）
• 进一步完善「股票数据分析软件」 - 01

后台回复「搜搜搜」，随机获取电子资源！

欢迎关注，请扫描二维码：

​