# 132 ms Python Using divide and conquer and merge 2 sorted lists

• ``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
#merge every two list
m = len(lists)
if m == 0:
return []
while m > 1:
ans_lis = []
for i in range(0,m,2):
if i+1 < m:
ans_lis.append(self.mergeTwoLists(lists[i],lists[i+1]))
else:
ans_lis.append(lists[i])
lists = ans_lis
m = len(lists)
if m > 0:
return lists[0]

def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 and l2:
if l1.val <= l2.val:
l1 = l1.next
else:
l2 = l2.next
elif l1:
return l1
elif l2:
return l2
else:
return None
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l2.next
point = point.next
#now, iterate through rest
if l1:
point.next = l1
if l2:
point.next = l2