fork download
copy 
  1. # Merge K Sorted Lists (LC version 3.05).
  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.     n = None
  14.     for x in reversed(seq):
  15.         n = ListNode(x, n)
  16.     return n
  17.  
  18. def printList(n):
  19.     a = []
  20.     while n:
  21.         a.append(n.val)
  22.         n = n.next
  23.     print('List(', a, ')', sep='')
  24.  
  25. # Merge.
  26.  
  27. def mergeKLists(lists):
  28.     if not lists:
  29.         return None
  30.  
  31.     # Push list heads to heap keyed on node.val and a secondary integer.
  32.     # The secondary keys serve a dual purpose:
  33.     #
  34.     #  1. The unique keys prevent the comparison from reaching the node
  35.     #     element which is not comparable.
  36.     #  2. The keys are ordered ascending with respect to the list input
  37.     #     ensuring stability for equal valued elements.
  38.  
  39.     heap = []
  40.     for k, n in enumerate(filter(None, lists)):
  41.         heappush(heap, (n.val, k, n))
  42.  
  43.     if not heap:
  44.         return None
  45.  
  46.     # The heap maintains the smallest valued head node for all lists at
  47.     # its front. The node is appended to the result and heap is updated
  48.     # with its next node as the new list head. The loop exits when only
  49.     # a single list remains.
  50.  
  51.     temp = ListNode()
  52.     t = temp
  53.     while True:
  54.         _, k, n = heappop(heap)
  55.         t.next = n
  56.         if not heap:
  57.             return temp.next
  58.         t = t.next
  59.         n = n.next
  60.         if n:
  61.             heappush(heap, (n.val, k, n))
  62.  
  63. # Show.
  64.  
  65. l0 = makeList([])
  66. l1 = makeList([1, 3, 5, 7])
  67. l2 = makeList([2, 4, 6])
  68. l3 = makeList([0, 4, 8])
  69.  
  70. printList(l0)
  71. printList(l1)
  72. printList(l2)
  73. printList(l3)
  74.  
  75. printList(mergeKLists([]))
  76. printList(mergeKLists([l0]))
  77. printList(mergeKLists([l1]))
  78. printList(mergeKLists([l1, l2, l3]))
Success #stdin #stdout 0.09s 14120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
List([])
List([1, 3, 5, 7])
List([2, 4, 6])
List([0, 4, 8])
List([])
List([])
List([1, 3, 5, 7])
List([0, 1, 2, 3, 4, 4, 5, 6, 7, 8])
https://ideone.com/nW7F8z
language:
Python 3 (python  3.12)
created:
11 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!