LeetCode之合并 K 個升序鏈表（Top 100）
作者：Swift君
給你一個鏈表數組，每個鏈表都已經按升序排列。請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。
前言
本題為 LeetCode 前 100 高頻題
我們社區陸續會將顧毅(Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。微博:@故胤道長[1])的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。
LeetCode 算法到目前我們已經更新了 22 期，我們會保持更新時間和進度(周一、周三、周五早上 9:00 發布)，每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。
不積跬步，無以至千里;不積小流，無以成江海，Swift社區 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。
難度水平：困難
1. 描述
給你一個鏈表數組，每個鏈表都已經按升序排列。
請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。
2. 示例
示例 1
輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數組如下：
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6
示例 2
輸入：lists = []
輸出：[]
示例 3
輸入：lists = [[]]
輸出：[]
約束條件：
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的總和不超過 10^4
3. 答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class MergeKSortedLists {
func mergeKLists(lists: [ListNode?]) -> ListNode? {
guard lists.count > 0 else {
return nil
}
var left = 0
var right = lists.count - 1
var lists = lists
while right > 0 {
left = 0
while left < right {
lists[left] = _mergeTwoLists(lists[left], lists[right])
left += 1
right -= 1
}
}
return lists[0]
}
private func _mergeTwoLists(l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var node = dummy
var l1 = l1
var l2 = l2
while l1 != nil && l2 != nil {
if l1!.val < l2!.val {
node.next = l1
l1 = l1!.next
} else {
node.next = l2
l2 = l2!.next
}
node = node.next!
}
node.next = l1 ?? l2
return dummy.next
}
- 主要思想：Dummy Node來遍歷兩個列表，比較兩個節點并指向右邊的一個。
- 時間復雜度：O(mlogn) m 表示一個列表的長度，n 表示列表的個數。
- 空間復雜度：O(1)
該算法題解的倉庫：LeetCode-Swift[2]
點擊前往 LeetCode[3] 練習
參考資料
[1]@故胤道長: https://m.weibo.cn/u/1827884772
[2]LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift
[3]LeetCode: https://leetcode.com/problems/merge-k-sorted-lists/
責任編輯：姜華
來源：
Swift社區
