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


  • 0
    P

    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:])])

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    C

    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).


  • 0
    C

    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):
        dummy = head = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
            head = head.next
        head.next = l1 or l2
        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)

Log in to reply
 

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