题干
Merge k Sorted Lists
Difficulty: Hard
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并K个已经排序的数组。
解题思路：
难度感觉算不上Hard（毕竟我做不出来的都是Hard），不过为了方便调试这次用了.net来写。
拿到题目最开始的反应是对于数组中的每一个链表都定义一个指针，每次遍历所有的指针，记录最小的值以及出现的位置，遍历完成后将最小值插入结果链表中，如果遍历后发现每一个指针都指向空节点则说明遍历完成。
最后成品：
public ListNode MergeKLists(ListNode[] lists)
{
ListNode head = null, cursor = null;
while (true)
{
var indexs = new List<int>();
var min = int.MaxValue;
for (var i = 0; i < lists.Length; i++)
{
if (lists[i] == null)
{
continue;
}
if (lists[i].val > min)
{
continue;
}
else
{
if (lists[i].val < min)
{
indexs.Clear();
min = lists[i].val;
}
indexs.Add(i);
}
}
if (min == int.MaxValue)
{
break;
}
else
{
for (var i = 0; i < indexs.Count; i++)
{
if (head == null)
{
head = new ListNode(min);
cursor = head;
}
else
{
cursor.next = new ListNode(min);
cursor = cursor.next;
}
lists[indexs[i]] = lists[indexs[i]].next;
}
}
}
return head;
}
Runtime: 112 ms 91.21%
时间复杂度O(K*log(N))
K是链表数组的长度，N是节点数量。
Memory Usage: 28.8 MB 8.33%
空间复杂度O(K+N)
其中O(N)指的是最后长度为N的排序后数组。
O(K)则是我为了存储指针位置而新建的List。
时间上我很满意了，但是空间复杂度看上去很高，试着去减少一下。
结果链表的空间肯定是不能省的，那么只能省去List了，每次只push一个最小值进去，只记录最小值以及最小值的位置
public ListNode MergeKLists(ListNode[] lists)
{
ListNode head = null, cursor = null;
while (true)
{
var index = -1;
var min = int.MaxValue;
for (var i = 0; i < lists.Length; i++)
{
if (lists[i] == null)
{
continue;
}
if (lists[i].val >= min)
{
continue;
}
else
{
min = lists[i].val;
index = i;
}
}
if (index == -1)
{
break;
}
else
{
if (head == null)
{
head = new ListNode(min);
cursor = head;
}
else
{
cursor.next = new ListNode(min);
cursor = cursor.next;
}
lists[index] = lists[index].next;
}
}
return head;
}
Runtime: 584 ms
Memory Usage: 29.3 MB
这样做肯定增加时间的，时间复杂度应该为（O(KN)），但是空间复杂度应该能缩减为O(N)。
但是结果让我大跌眼镜，空间占用不减反增，这里是实在不能理解。
其余解法
回去翻看LeetCode上的solution，他列出了五种解法。
最简单的应该就是暴力求解了，将所有的链表中的节点都push到一个数组中，排序后生成新的链表。
时间O(N*log(N))，空间O(N)。
另一个Smart Play则是将问题简化为(K-1)次合并两个排序数组，我个人觉得思路比我的好，很多复杂问题都能简化为多个简单问题的累加。时间复杂度O(KN)，空间复杂度O(1)。
最后一种解法则是上一个方法的改进，每次合并floor(k/2)个数组，这样合并次数就被减少到ceil(log2(k))次了。这样就减少了数组中大部分链表的结点需要排序的次数，而后几个链表的元素排序次数则会略有增加，大部分情况下优于上面的解。除非最后一个链表节点特别多，其余链表节点特别少，这样的话上一个做法会优于这个。
