一、前言：
本文將描述Merge k Sorted Lists的算法實(shí)現(xiàn)和分析废封。
算法題目：將K個(gè)排序好的鏈表合并州泊。
算法思路：
1. 使用堆排序方式來合并鏈表
2. 使用合并兩個(gè)鏈表的方法
算法復(fù)雜度分析：在兩個(gè)算法實(shí)現(xiàn)之后會(huì)有相關(guān)分析。
二漂洋、算法實(shí)現(xiàn)：
1遥皂、推排序合并鏈表（java中的優(yōu)先隊(duì)列）
在我發(fā)布的其他文章中有一篇專門提到推排序的實(shí)現(xiàn)力喷，在這里，使用的是Swift演训，實(shí)現(xiàn)過程也比較簡(jiǎn)單弟孟。但是其實(shí)現(xiàn)是使用的數(shù)組而不是鏈表，所以針對(duì)鏈表的堆在Swift中需要重新實(shí)現(xiàn)样悟。
鏈表堆需要實(shí)現(xiàn)的協(xié)議
/// 堆協(xié)議
protocol Heep {
associatedtype T
func add(t: T) // 加入一個(gè)元素
func poll() -> T // 返回頂元素
func isEmpty() -> Bool // 是否為空
}
假設(shè)ListNode_Heap實(shí)現(xiàn)了相關(guān)協(xié)議拂募，是一個(gè)鏈表小頂堆（實(shí)際上沒有）
class ListNode_Heap: Heep {
typealias T = ListNode
func add(t: ListNode) {}
func poll() -> ListNode { return ListNode.init(-1) }
func isEmpty() -> Bool { return true }
}
開始實(shí)現(xiàn)合并鏈表的算法：
算法思路，挨個(gè)將元素加入到大頂堆中陈症，再將小頂堆的頂順序加入到另一個(gè)鏈表中。
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
let h = ListNode_Heap() // 創(chuàng)建一個(gè)小頂堆
for node in lists {
if node != nil {
h.add(t: node!)
}
} // 這里將所有元素加入到了堆中
let dummy = ListNode(0) // 新建鏈表的頭
var tail: ListNode? = dummy // 遍歷節(jié)點(diǎn)
while !h.isEmpty() {
tail!.next = h.poll()
tail = tail!.next
if tail!.next != nil {
h.add(t: tail!.next!)
}
} // 將堆中元素挨個(gè)輸出，達(dá)到新建鏈表效果
return dummy.next
}
算法分析：
設(shè)k個(gè)鏈表中總共有n個(gè)節(jié)點(diǎn)。
先不考慮Heap的時(shí)間復(fù)雜度卦溢，則上述函數(shù)的操作是O（lg n）的吐辙。
但是將Heap的操作時(shí)間復(fù)雜度加入計(jì)算后發(fā)現(xiàn)，函數(shù)進(jìn)行了n次add（）和n次poll（）。add和poll的負(fù)責(zé)度都是O（lg n）孵构，所以上述總體時(shí)間復(fù)雜度是：2n（lg n），也就是O（n*lgn）官还。
2、使用Merge two sorted lists的方法來
合并兩個(gè)已排序的列表的方法如下：
這是一個(gè)比較簡(jiǎn)單的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
}
}
利用這個(gè)算法，我們將k個(gè)列表想象成2*p = k，那我們需要合并兩個(gè)鏈表合并（log2 p）次，因?yàn)檫@類似一個(gè)二叉樹粹舵，每次合并連個(gè)鏈表历涝，就會(huì)生成自己的父節(jié)點(diǎn)堰塌，然后父節(jié)點(diǎn)再去合并。所以整個(gè)時(shí)間復(fù)雜度就是O(n*lg k), 所以當(dāng)每個(gè)鏈表的節(jié)點(diǎn)數(shù)比較大的時(shí)候恤煞，這個(gè)算法要略好于使用堆來排序。
開始實(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!) // 尾遞歸
}
}
三竿裂、尾巴
本文主要實(shí)現(xiàn)了Leet Code中23. Merge k Sorted Lists的兩個(gè)解決算法，兩種算法的時(shí)間復(fù)雜度都比較接近影斑，各有優(yōu)劣皆辽。
