8.4. heapq — Heap queue algorithm — Python 2.7.10 documentation

https://docs.python.org/2/library/heapq.html



8.4. heapq — Heap queue algorithm — Python 2.7.10 documentation:

6.3
Merge k Sorted Lists

描述

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

分析

可以复用Merge
Two Sorted Lists（见§6.2）的函数

//LeetCode,
Merge k Sorted Lists

//
时间复杂度O(n1+n2+...)，空间复杂度O(1)

#
Definition for singly-linked list.

#
class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class
Solution:

    # @param {ListNode[]} lists

    # @return {ListNode}

    def mergeKLists(self, lists):

        heap = []

        for node in lists:

            if node:

                heap.append((node.val, node))

        heapq.heapify(heap)

        head = ListNode(0); curr = head

        while heap:

            pop = heapq.heappop(heap)

            curr.next = ListNode(pop[0])

            curr = curr.next

            if pop[1].next:

                heapq.heappush(heap,
(pop[1].next.val, pop[1].next))

        return head.next

'via Blog this'