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 34
|
class Solution: """ create a list ans. create a array A. A[i] stores the pointer of lists[i] create a priority queue named Q. For each pointer i in A, we add A[i].val to Q. While Q is not empty, do: get pointer i and value x from Q, add x to res after move forward the pointer i, if i is not null, then add i'.val, i' to Q. """ def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: A,Q=[],[] ans=ListNode() w=ans for p in lists: if p is not None: A.append(p) for i,p in enumerate(A): heapq.heappush(Q,(p.val,i,p)) while len(Q) > 0: x,i,p=heapq.heappop(Q) w.next=ListNode(x) w=w.next p=p.next if p is not None: heapq.heappush(Q,(p.val,i,p)) return ans.next
|