Python Code that avoids TLE


  • 1
    B
    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head or not head.next:
            return head
        
        vhead=ListNode(0)
        vhead.next=head
        cur=vhead
        scan=vhead
        
        inserted=0
        
        while cur.next:
            inserted=0
            
            if scan.next.val>cur.next.val:
                scan=vhead
            
            while scan.next!=cur.next:
                if scan.next.val>cur.next.val:
                    # do the insertion here
                    node=cur.next
                    cur.next=node.next
                    node.next=scan.next
                    scan.next=node
                    inserted=1
                    
                    break
                
                scan=scan.next
            
            if not inserted:
                cur=cur.next
                
        return vhead.next
    

    The idea to avoid time limit exceed is to add

    if scan.next.val>cur.next.val:
                scan=vhead
    

    so that not every scan is from the beginning of the list. kind of special optimization in the list case since for array it is not necessary.


Log in to reply
 

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