Python Recursive Solution. How to compute the Complexity in recursive Algorithm?[166ms]

• n is the length of input-list
m is the expected length of Linked-List

Time Complexity: O(nlognm)
Space Complexity: O(nlognm)

Is That RIGHT?

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

class Solution:
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def mergeTwoLists(self, l1, l2):
l = ListNode(0)
c = l
p = None
if l1 is None:
return l2
if l2 is None:
return l1

while l1 is not None and l2 is not None:
if l1.val < l2.val:
c.next = l1
l1 = l1.next
else:
c.next = l2
l2 = l2.next
c = c.next
if l1 is None:
c.next = l2
if l2 is None:
c.next = l1

return l.next
# @param {ListNode[]} lists
# @return {ListNode}
def mergeKLists(self, lists):
if len(lists) == 0:
return None
elif len(lists) == 1:
return lists[0]
elif len(lists) == 2:
return self.mergeTwoLists(*lists)
else:
half = int(len(lists)/2 + len(lists)%2)
return self.mergeKLists([self.mergeKLists(lists[:half]),
self.mergeKLists(lists[half:])])``````

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• The time and space complexities you computed are correct in my opinion. If you are using divide and conquer recursion method, in every intermediate stage, the number of total nodes should be nm, where n is the number of lists and m is the average length of every list. So the required space of every stage should be O(nm). The time complexity of every stage is O(nm) as well, as these nodes are merged by all the smaller lists. There are tolly logn stages. So the time and space complexity both are O(nm*logn).

• Here is a concise version of your idea:

``````def mergeKLists(self, lists):
if not lists:
return None
if len(lists) == 1:
return lists[0]
l1 = self.mergeKLists(lists[:len(lists)//2])
l2 = self.mergeKLists(lists[len(lists)//2:])
return self.merge(l1, l2)

def merge(self, l1, l2):
while l1 and l2:
if l1.val < l2.val:
l1 = l1.next
else:
l2 = l2.next
return dummy.next
``````

In order to not split the original lists, we can input the start and end indexes as parameters as well. In this way, it costs less memory:

``````def mergeKLists(self, lists):
return self.helper(lists, 0, len(lists)-1)

def helper(self, lists, start, end):
if start > end:
return None
if start == end:
return lists[start]
mid = (start+end) >> 1
# the left part should not be less
l1 = self.helper(lists, start, mid)
l2 = self.helper(lists, mid+1, end)
return self.merge(l1, l2)``````

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