Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution
- 维护一个最小堆，保存当前各个List中的第一个节点
- 最小堆的第一个节点就是当前最小节点
(Merge-k-sorted-lists.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| # 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
"""
# heap[i] : (node, node.val)
heap = []
for root in lists:
if root:
heapq.heappush(heap,(root.val, root))
head = ListNode(-1)
ret = head
while heap:
smallestNode = heapq.heappop(heap)[1]
head.next = smallestNode
head = head.next
if smallestNode.next:
heapq.heappush(heap,(smallestNode.next.val, smallestNode.next))
return ret.next
|