Python solution using Merge Sort-O(n*log(k))


  • 0
    L
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode[]} lists
        # @return {ListNode}
        def mergeKLists(self, lists):
            if not lists:
                return None
            l = len(lists)
            if l == 1:
                return lists[0]
            mid = l//2
            return self.mergeLists(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:]))
        
        def mergeLists(self, list1, list2):
            p, q = list1, list2
            head = tail = None
            while p and q:
                if p.val < q.val:
                    if not tail:
                        head = p
                        tail = p
                        p = p.next
                    else:
                        tail.next = p
                        tail = tail.next
                        p = p.next
                else:
                    if not tail:
                        head = q
                        tail = q
                        q = q.next
                    else:
                        tail.next = q
                        tail = tail.next
                        q = q.next
                                
            if p:
                if not tail:
                    head = p
                    tail = p
                else:
                    tail.next = p
            if q:
                if not tail:
                    head = q
                    tail = q
                else:
                    tail.next = q
            if not tail:
                return None
            else:
                return head

  • 0
    C

    While the time and space complexities in your case should both be O(nmlogn), where n is the number of lists and m is the average length of every list, right?


Log in to reply
 

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