-
Notifications
You must be signed in to change notification settings - Fork 0
/
23.py
32 lines (32 loc) · 1.02 KB
/
23.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
import heapq
# Definition for singly-linked list.
# LEETCODE HARD
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
pointers = []
heapify(pointers)
for i,l in enumerate(lists):
if l:
heappush(pointers,(l.val,i))
lists[i] = lists[i].next
if pointers:
val, idx = heappop(pointers)
if lists[idx]:
heappush(pointers,(lists[idx].val,idx))
lists[idx] = lists[idx].next
new_list = ListNode(val)
cur = new_list
else:
new_list = None
while pointers:
val, idx = heappop(pointers)
if lists[idx]:
heappush(pointers,(lists[idx].val,idx))
lists[idx] = lists[idx].next
cur.next = ListNode(val)
cur = cur.next
return new_list