My AC python solution for your reference.


  • 2
    L

    merge left half part, and right half part.

    class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        if(len(lists)==0):return None;
        if(len(lists)==1):return lists[0];
        else:
            left=len(lists)//2;
            pl=self.mergeKLists(lists[0:left]);
            pr=self.mergeKLists(lists[left:]);
            
            result=ListNode(-1);
            p=result;
            while(pl!=None or pr!=None):
                if(pr==None or ((pl!=None) and pl.val<=pr.val)):
                    p.next=ListNode(pl.val);
                    pl=pl.next;
                else:
                    p.next=ListNode(pr.val);
                    pr=pr.next;
                p=p.next;
            
            return result.next;

  • 0
    I

    I think when merging pl and pr, p.next=ListNode(pl.val) can be p.next=pl to save memory-use.


  • 0
    C

    I used like the same method, but my runtime is 660ms, how about yours?


  • 0
    I

    707ms. The recursive solution will cause more time than the for-loop solution.


Log in to reply
 

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