[Leetcode]23. 合并K个排序链表

题目描述：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

我的方法：

可以用递归或者直接循环，将k个排序链表转换为2个链表的排序。假如用递归的方法：

1. 对于输入lists而言，可以将其转换为list[0]和slef.mergeKLists(lists[1:])。
2. 终止条件是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

如果直接用循环来解决呢？基本思路如下：

1. 记录当前已经完成合并排序的链表l。
2. 对于lists中的每一个链表，将其与链表l合并排序，排序方法同两个有序链表的合并。
3. 直至循环完成。

循环的速度要快一点：执行用时 : 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