Why my insertionSortList get TLE?


  • 0
    Z

    My python code for insertionSortList get TLE? I don't konw the reason. In the condition of almost ordered or almost reverse order, I make optimization,but It stil not accepted. The last executed input is {5000, 4999, ..., 3, 2, 1}?

    class Solution:

    def adjust_list(self, head):
        size = 0
        inv_size = 0
        
        curr = head
        while curr:
            if curr.next and (curr.val > curr.next.val):
                inv_size += 1
            size += 1
            curr = curr.next
        
        if (size < 100) or (float(inv_size)/float(size) < 0.7):
            return (head, False)
        else:
            dumpy = ListNode(0)
            while head:
                t = head.next
                head.next = dumpy.next
                dumpy.next = head
                head = t
            
            if inv_size + 1 == size:
                return (dumpy.next, True)
            else:
                return (dumpy.next, False)
        
    # return the last node of the ordered list;
    # @phead : the last node of the ordered list
    def move(self, order_last):
    
        if not order_last : return None
        
        while order_last and order_last.next:
            if order_last.val <= order_last.next.val:
                order_last = order_last.next
            else:
                break
        if not order_last.next:
            return None
        else:
            return order_last
    
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        
        head, ordered = self.adjust_list(head)
        if ordered: return head
        
        dumpy = ListNode(0)
        dumpy.next = head
        order_last = dumpy.next
        pcurr = dumpy
        
        while True:
            order_last = self.move(order_last)
    
            if not order_last : break
    
            # print 'val : ' + str(order_last.val)
            
            # do insert sort, one node per loop
            hit = order_last.next
            order_last.next = hit.next
            
            if hit.val < pcurr.next.val:
                pcurr = dumpy
            #pcurr = dumpy
            while pcurr.next:
                # print 'pcurr next value : ' + str(pcurr.next.val)
                # print 'hit val : ' + str(hit.val)
                if pcurr.next.val >= hit.val: break
                
                pcurr = pcurr.next
            
            hit.next = pcurr.next
            pcurr.next = hit
            
            # print 'order_list val : ' + str(order_last.val)
            # print 'order_list.next val : ' + str(order_last.next.val)
            # print 'head val : '  + str(dumpy.next.val)
            
        return dumpy.next`

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    C

    I think the reason is that you're using python. My code has the same trouble while I'm using python. But my code was accepted when I translate my code to C++. Maybe using C++ is the right way to solve such problems.


Log in to reply
 

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