题目描述：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
我的方法：
可以用递归或者直接循环，将k个排序链表转换为2个链表的排序。假如用递归的方法：
- 对于输入lists而言，可以将其转换为list[0]和slef.mergeKLists(lists[1:])。
- 终止条件是len(lists)为1。
但是递归的耗时太长，用以下方法会超时。时间复杂度为len(lists)len(ListNode)2，感觉还好啊。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
# 递归解法
if len(lists)>1:
tmp0=lists[0]
tmp1=self.mergeKLists(lists[1:])
ans=ListNode(0)
head=ans
while tmp0 and tmp1:
if tmp0.val<=tmp1.val:
ans.next=tmp0
tmp0=tmp0.next
else:
ans.next=tmp1
tmp1=tmp1.next
ans=ans.next
ans.next=tmp0 if tmp0 else tmp1
return head.next
# 终止条件：考虑lists只有一个元素或为空的情况
elif len(lists)==1:
return lists[0]
else:
return ListNode(0).next
如果直接用循环来解决呢？基本思路如下：
- 记录当前已经完成合并排序的链表l。
- 对于lists中的每一个链表，将其与链表l合并排序，排序方法同两个有序链表的合并。
- 直至循环完成。
循环的速度要快一点：执行用时 : 7268 ms, 在Merge k Sorted Lists的Python提交中击败了4.07% 的用户。内存消耗 : 17.4 MB, 在Merge k Sorted Lists的Python提交中击败了39.18% 的用户。但还是很慢。
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
# 结果链表
ans=ListNode(None)
head=ans
# 循环两两排序和整合
for l in lists:
tmp=ListNode(0)
tmp_head=tmp
while ans and l:
if ans.val<=l.val:
tmp.next=ans
ans=ans.next
else:
tmp.next=l
l=l.next
tmp=tmp.next
tmp.next=ans if ans else l
ans=tmp_head.next
return head.next
别人的解法：
直接将多个ListNode的排序转换为数组的排序，就快了很多。省去了大量的比较操作。排名虽然不算靠前，但耗时降低明显：执行用时 : 120 ms, 在Merge k Sorted Lists的Python提交中击败了41.86% 的用户。内存消耗 : 17.4 MB, 在Merge k Sorted Lists的Python提交中击败了39.18% 的用户。
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
# 将多个数组整合为1个数组
node_list=[]
for i in lists:
while i:
node_list.append(i)
i=i.next
# 对单个数组排序
node_list.sort(key=lambda x:x.val)
ans=ListNode(0)
head=ans
# 数组转换为链表
for i in node_list:
ans.next=i
ans=ans.next
return head.next
