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

後臺回覆「搜搜搜」，隨機獲取電子資源！

歡迎關注，請掃描二維碼：

​