Python 98ms using counting sort


  • 0
    C

    O(n + m) time where n is the total number of elements in all of the lists and m is the difference between the minimum and maximum valued elements. Faster than 98.99% of python solutions.

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            if not lists:
                return None
            min_value = float('inf')
            max_value = float('-inf')
            for i in range(len(lists)):
                current = lists[i]
                while current is not None:
                    min_value = min(min_value, current.val)
                    max_value = max(max_value, current.val)
                    current = current.next
            if min_value == float('inf'):
                return None
            buckets = [[] for _ in range(max_value - min_value + 1)]
            for i in range(len(lists)):
                current = lists[i]
                while current is not None:
                    buckets[current.val - min_value].append(current)
                    current = current.next
            head = ListNode(None)
            current = head
            for i in range(len(buckets)):
                for j in range(len(buckets[i])):
                    current.next = buckets[i][j]
                    current = current.next
            current.next = None
            return head.next
    

Log in to reply
 

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