[leetcode]Merge k Sorted Lists @ Python

原题地址:https://oj.leetcode.com/problems/merge-k-sorted-lists/

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

解题思路:归并k个已经排好序的链表。使用堆这一数据结构,首先将每条链表的头节点进入堆中,然后将最小的弹出,并将最小的节点这条链表的下一个节点入堆,依次类推,最终形成的链表就是归并好的链表。

代码:

[leetcode]Merge k Sorted Lists @ Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a 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
[leetcode]Merge k Sorted Lists @ Python

 

[leetcode]Merge k Sorted Lists @ Python,布布扣,bubuko.com

[leetcode]Merge k Sorted Lists @ Python

上一篇:为什么C++空类的实例大小为1


下一篇:[笔记]JAVA内存模型与线程