-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeKLL.py
33 lines (29 loc) · 873 Bytes
/
MergeKLL.py
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
29
30
31
32
33
# Problem: https://leetcode.com/problems/merge-k-sorted-lists/description/
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
import heapq
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
h = []
if not lists:
return []
for l in lists:
if l:
heapq.heappush(h, (l.val, l))
if not h:
return []
root = heapq.heappop(h)[1]
curr = root
while h:
if curr.next is not None:
heapq.heappush(h, (curr.next.val, curr.next))
curr.next = heapq.heappop(h)[1]
curr = curr.next
return root