# Python Divide Conquer & k Heap

• Divide Conquer

Just use merge sort's idea to divide k lists and merge each two lists recursively. Time complexity is O(nlogk) assuming n is the total number of nodes.

def mergeKLists(self, lists):
def merge(l1, l2):
p = head = ListNode(0) # dummy node
while l1 or l2:
if l1 and l2:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next

elif l1 is None:
p.next = l2
break
elif l2 is None:
p.next = l1
break

def divide(lists, start, end):
if start == end:
return lists[start]
mid = start + (end - start) / 2
l1 = divide(lists, start, mid)
l2 = divide(lists, mid + 1, end)
return merge(l1, l2)

return divide(lists, 0, len(lists) - 1) if lists else []

K heap

Use a heap of size k to pop the smallest element from each list and push the next element into the heap util every element is in and out from the heap.

def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
import heapq
p = dummy = ListNode(-1)
h = []
for i in range(len(lists)):
if lists[i] > 0:
heapq.heappush(h, (lists[i].val, lists[i]))

while h:
curr = heapq.heappop(h)
currlist = curr[1]
p.next = currlist
p = p.next
if currlist.next:
heapq.heappush(h, (currlist.next.val, currlist.next))

return dummy.next

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.