一、前言：
本文将描述Merge k Sorted Lists的算法实现和分析。
算法题目：将K个排序好的链表合并。
算法思路：
1. 使用堆排序方式来合并链表
2. 使用合并两个链表的方法
算法复杂度分析：在两个算法实现之后会有相关分析。
二、算法实现：
1、推排序合并链表（java中的优先队列）
在我发布的其他文章中有一篇专门提到推排序的实现，在这里，使用的是Swift，实现过程也比较简单。但是其实现是使用的数组而不是链表，所以针对链表的堆在Swift中需要重新实现。
链表堆需要实现的协议
/// 堆协议
protocol Heep {
associatedtype T
func add(t: T) // 加入一个元素
func poll() -> T // 返回顶元素
func isEmpty() -> Bool // 是否为空
}
假设ListNode_Heap实现了相关协议，是一个链表小顶堆（实际上没有）
class ListNode_Heap: Heep {
typealias T = ListNode
func add(t: ListNode) {}
func poll() -> ListNode { return ListNode.init(-1) }
func isEmpty() -> Bool { return true }
}
开始实现合并链表的算法：
算法思路，挨个将元素加入到大顶堆中，再将小顶堆的顶顺序加入到另一个链表中。
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
let h = ListNode_Heap() // 创建一个小顶堆
for node in lists {
if node != nil {
h.add(t: node!)
}
} // 这里将所有元素加入到了堆中
let dummy = ListNode(0) // 新建链表的头
var tail: ListNode? = dummy // 遍历节点
while !h.isEmpty() {
tail!.next = h.poll()
tail = tail!.next
if tail!.next != nil {
h.add(t: tail!.next!)
}
} // 将堆中元素挨个输出，达到新建链表效果
return dummy.next
}
算法分析：
设k个链表中总共有n个节点。
先不考虑Heap的时间复杂度，则上述函数的操作是O（lg n）的。
但是将Heap的操作时间复杂度加入计算后发现，函数进行了n次add（）和n次poll（）。add和poll的负责度都是O（lg n），所以上述总体时间复杂度是：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）次，因为这类似一个二叉树，每次合并连个链表，就会生成自己的父节点，然后父节点再去合并。所以整个时间复杂度就是O(n*lg k), 所以当每个链表的节点数比较大的时候，这个算法要略好于使用堆来排序。
开始实现算法
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!) // 尾递归
}
}
三、尾巴
本文主要实现了Leet Code中23. Merge k Sorted Lists的两个解决算法，两种算法的时间复杂度都比较接近，各有优劣。
