Main idea: instead of loop through K lists and find the minimun val, use D&C to merge per 2 lists first so k lists turn into k/2 with avg length N/(k/2), then into k/4 and so on; time complexity: each time we traverse almost N nodes, but repeat this procedure lgN time
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists)//2
l,r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
return self.merge(l,r)
def merge(self,l,r):
dummy = p = ListNode()
if not l or not r:
return l or r
while l and r:
if l.val <= r.val:
p.next = l
l = l.next
else:
p.next = r
r = r.next
p = p.next
if l or r :
p.next = l or r
return dummy.next
def merge1(self,l,r):
if not l or not r:
return l or r
if l.val <= r.val:
l.next = self.merge1(l.next,r)
return l
r.next = self.merge1(l,r.next)
return r