Can it be better than O(NlogN)?


  • 0
    T

    just a simple solution, took 105msec = { merge - sort - convert }
    I think this approach takes O(nlogn) average time if a system has enough memory.

    class Solution(object):
        def mergeKLists(self, lists):
            merged_list = []
            
            # merge into one list: O(n)
            for list_k in lists:
                node = list_k
                while node != None:
                    merged_list.append(node.val)
                    node = node.next
            if len(merged_list) < 1:
                return None
            
            # sort in a list: O(nlogn)
            sorted_list = sorted(merged_list)
            
            # convert python list to ListNode: O(n)
            head = prev = ListNode(sorted_list[0])
            for i in range(1, len(sorted_list)):
                newnode = ListNode(sorted_list[i])
                prev.next = newnode
                prev = newnode
            
            return head
    

Log in to reply
 

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