132 ms Python Using divide and conquer and merge 2 sorted lists


  • 0
    Y
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            #merge every two list
            m = len(lists)
            if m == 0:
                return []
            while m > 1:
                ans_lis = []
                for i in range(0,m,2):
                    if i+1 < m:
                        ans_lis.append(self.mergeTwoLists(lists[i],lists[i+1]))
                    else:
                        ans_lis.append(lists[i])
                lists = ans_lis
                m = len(lists)
            if m > 0:
                return lists[0]
                
                    
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            #determine the head
            if l1 and l2:
                if l1.val <= l2.val:
                    head = l1
                    l1 = l1.next
                else:
                    head = l2
                    l2 = l2.next
            elif l1:
                return l1
            elif l2:
                return l2
            else:
                return None
            point = head
            while l1 and l2:
                if l1.val <= l2.val:
                    point.next = l1
                    l1 = l1.next
                else:
                    point.next = l2
                    l2 = l2.next
                point = point.next
            #now, iterate through rest
            if l1:
                point.next = l1
            if l2:
                point.next = l2
            return head

Log in to reply
 

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