本文共 1556 字，大约阅读时间需要 5 分钟。

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:[  1->4->5,  1->3->4,  2->6]Output: 1->1->2->3->4->4->5->6

第一想法很简单，把lists中所有value存进一个列表中，再对列表进行排序，然后根据排序重新构造新的链表。这种方法速度很快，内存占用较多，代码如下：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def mergeKLists(self, lists):        """        :type lists: List[ListNode]        :rtype: ListNode        """        newlist=[]        for list in lists:            while list:                newlist.append(list.val)                list = list.next        newlist.sort()                head = p = ListNode(0)        for node in newlist:            p.next = ListNode(node)            p = p.next                    return head.next

同时也学习了python的heapq库函数，有关于堆，可以进行自动排序，不过这样速度会更慢，内存占用基本没有变化。关于heapq函数使用，参考

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def mergeKLists(self, lists):        """        :type lists: List[ListNode]        :rtype: ListNode        """        import heapq                heap=[]        for linklist in lists:            while linklist:                heapq.heappush(heap, linklist.val)                linklist = linklist.next                head = p = ListNode(0)                for i in range(len(heap)):            p.next = ListNode(heapq.heappop(heap))            p = p.next        return head.next

转载地址：http://fbrbb.baihongyu.com/