fork(1) download
copy 
  1. # Merge K Sorted Lists (LC version 3.00).
  2.  
  3. from heapq import heappush, heappop
  4.  
  5. # List.
  6.  
  7. class ListNode:
  8.     def __init__(self, val=None, next=None):
  9.         self.val = val
  10.         self.next = next
  11.  
  12. def makeList(seq):
  13.     t = None
  14.     for x in reversed(seq):
  15.         t = ListNode(x, t)
  16.     return t
  17.  
  18. def printList(l):
  19.     a = []
  20.     while l:
  21.         a.append(l.val)
  22.         l = l.next
  23.     print('List:', a)
  24.  
  25. # Merge.
  26.  
  27. def mergeKLists(lists):
  28.     heap = []
  29.     for k, n in enumerate(lists):
  30.         if n:
  31.             heappush(heap, (n.val, k, n))
  32.     temp = ListNode()
  33.     t = temp
  34.     while heap:
  35.         _, k, n = heappop(heap)
  36.         t.next = n
  37.         t = t.next
  38.         n = n.next
  39.         if n:
  40.             heappush(heap, (n.val, k, n))
  41.     return temp.next
  42.  
  43. # Show.
  44.  
  45. l1 = makeList([1, 3, 5, 7])
  46. l2 = makeList([2, 4, 6])
  47. l3 = makeList([0, 4, 8])
  48.  
  49. printList(l1)
  50. printList(l2)
  51. printList(l3)
  52. printList(mergeKLists([l1, l2, l3]))
Success #stdin #stdout 0.09s 14096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
List: [1, 3, 5, 7]
List: [2, 4, 6]
List: [0, 4, 8]
List: [0, 1, 2, 3, 4, 4, 5, 6, 7, 8]
https://ideone.com/2aOJ12
language:
Python 3 (python  3.12)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!