日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

前言

我們社區(qū)陸續(xù)會(huì)將顧毅(Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。微博:@故胤道長(zhǎng)[1])的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。

LeetCode 算法到目前我們已經(jīng)更新了 22 期，我們會(huì)保持更新時(shí)間和進(jìn)度(周一、周三、周五早上 9:00 發(fā)布)，每期的內(nèi)容不多，我們希望大家可以在上班路上閱讀，長(zhǎng)久積累會(huì)有很大提升。

不積跬步，無(wú)以至千里;不積小流，無(wú)以成江海，Swift社區(qū) 伴你前行。如果大家有建議和意見(jiàn)歡迎在文末留言，我們會(huì)盡力滿足大家的需求。

難度水平：困難

1. 描述

給你一個(gè)鏈表數(shù)組，每個(gè)鏈表都已經(jīng)按升序排列。

請(qǐng)你將所有鏈表合并到一個(gè)升序鏈表中，返回合并后的鏈表。

2. 示例

示例 1

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋?zhuān)烘湵頂?shù)組如下：
[
  1->4->5,
  1->3->4,
  2->6
]
將它們合并到一個(gè)有序鏈表中得到。
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 的總和不超過(guò) 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來(lái)遍歷兩個(gè)列表，比較兩個(gè)節(jié)點(diǎn)并指向右邊的一個(gè)。
• 時(shí)間復(fù)雜度：O(mlogn) m 表示一個(gè)列表的長(zhǎng)度，n 表示列表的個(gè)數(shù)。
• 空間復(fù)雜度：O(1)

該算法題解的倉(cāng)庫(kù)：LeetCode-Swift[2]

點(diǎn)擊前往 LeetCode[3] 練習(xí)

參考資料

[1]@故胤道長(zhǎng): 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/

當(dāng)前名稱(chēng)：LeetCode之合并K個(gè)升序鏈表（Top100）
文章URL：http://www.5511xx.com/article/djcegoo.html