一、前言：

本文將描述Merge k Sorted Lists的算法實現(xiàn)和分析。
算法題目：將K個排序好的鏈表合并。
算法思路：
1. 使用堆排序方式來合并鏈表
2. 使用合并兩個鏈表的方法
算法復(fù)雜度分析：在兩個算法實現(xiàn)之后會有相關(guān)分析。

二、算法實現(xiàn)：

1、推排序合并鏈表（java中的優(yōu)先隊列）

在我發(fā)布的其他文章中有一篇專門提到推排序的實現(xiàn)，在這里，使用的是Swift，實現(xiàn)過程也比較簡單。但是其實現(xiàn)是使用的數(shù)組而不是鏈表，所以針對鏈表的堆在Swift中需要重新實現(xiàn)。
鏈表堆需要實現(xiàn)的協(xié)議

/// 堆協(xié)議
protocol Heep {
    associatedtype T
    func add(t: T) // 加入一個元素
    func poll() -> T // 返回頂元素
    func isEmpty() -> Bool // 是否為空
}

假設(shè)ListNode_Heap實現(xiàn)了相關(guān)協(xié)議，是一個鏈表小頂堆（實際上沒有）

class ListNode_Heap: Heep {
    typealias T = ListNode
    func add(t: ListNode) {}
    func poll() -> ListNode { return ListNode.init(-1) }
    func isEmpty() -> Bool { return true }
}

開始實現(xiàn)合并鏈表的算法：
算法思路，挨個將元素加入到大頂堆中，再將小頂堆的頂順序加入到另一個鏈表中。

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        let h = ListNode_Heap() // 創(chuàng)建一個小頂堆
        for node in lists {
            if node != nil {
                h.add(t: node!)
            }
        } // 這里將所有元素加入到了堆中
        
        let dummy = ListNode(0) // 新建鏈表的頭
        var tail: ListNode? = dummy // 遍歷節(jié)點
        
        while !h.isEmpty() {
            tail!.next = h.poll()
            tail = tail!.next
            
            if tail!.next != nil {
                h.add(t: tail!.next!)
            }
        } // 將堆中元素挨個輸出，達(dá)到新建鏈表效果
        return dummy.next
    }

算法分析：
設(shè)k個鏈表中總共有n個節(jié)點。
先不考慮Heap的時間復(fù)雜度，則上述函數(shù)的操作是O（lg n）的。
但是將Heap的操作時間復(fù)雜度加入計算后發(fā)現(xiàn)，函數(shù)進(jìn)行了n次add（）和n次poll（）。add和poll的負(fù)責(zé)度都是O（lg n），所以上述總體時間復(fù)雜度是：2n（lg n），也就是O（n*lgn）。

2、使用Merge two sorted lists的方法來

合并兩個已排序的列表的方法如下：
這是一個比較簡單的O（n）算法，但是不是尾遞歸。

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        } else if l2 == nil {
            return l1
        }
        
        
        if (l1?.val)! > (l2?.val)! {
            let newNode = ListNode((l2?.val)!)
            newNode.next = mergeTwoLists(l1, l2?.next)
            return newNode
        } else {
            let newNode = ListNode((l1?.val)!)
            newNode.next = mergeTwoLists(l1?.next, l2)
            return newNode
        }
    }

利用這個算法，我們將k個列表想象成2*p = k，那我們需要合并兩個鏈表合并（log2 p）次，因為這類似一個二叉樹，每次合并連個鏈表，就會生成自己的父節(jié)點，然后父節(jié)點再去合并。所以整個時間復(fù)雜度就是O(n*lg k), 所以當(dāng)每個鏈表的節(jié)點數(shù)比較大的時候，這個算法要略好于使用堆來排序。
開始實現(xiàn)算法

func mergeKLists2(_ lists: [ListNode?]) -> ListNode? {
        var arr = lists
        let mergeTwoList = Merge_Two_Sorted_Lists()
        if lists.count > 2 {
            let count = arr.count
            let l1 = arr.remove(at: count-1)
            let l2 = arr.remove(at: count-2)
            let newNode = mergeTwoList.mergeTwoLists(l1, l2)
            arr.append(newNode)
            return self.mergeKLists2(arr) // 尾遞歸
        } else {
            return mergeTwoList.mergeTwoLists(lists.first!, lists.last!) // 尾遞歸
        }
    }

三、尾巴

本文主要實現(xiàn)了Leet Code中23. Merge k Sorted Lists的兩個解決算法，兩種算法的時間復(fù)雜度都比較接近，各有優(yōu)劣。