Can it be better than O(NlogN)?

  • 0

    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:
                    node =
            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])
       = 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.