The python time limit does not make sense!!!!


  • 2
    H

    Here is my code:

    def insertionSortList(head):
        dummy = ListNode(0)
        dummy.next = head
        last = p = q = dummy
        while p and p.next:
            q = dummy if p.next.val < last.next.val else last
            while q != p and q.next and q.next.val < p.next.val:
                q = q.next
               
            #insert
            if p != q:
                print('swap',p.val, q.val)
                tmp  = p.next
                p.next = tmp.next
                tmp.next = q.next
                q.next = tmp
            else:
                p = p.next
            last = q
            
    
        return dummy.next
    

    I have some optimization to reduce the run time and the algorithm becomes linear time in extreme case like below:

    0,6,5,4,3,2,1
    swap 6 0
    0,5,6,4,3,2,1
    swap 6 0
    0,4,5,6,3,2,1
    swap 6 0
    0,3,4,5,6,2,1
    swap 6 0
    0,2,3,4,5,6,1
    swap 6 0
    0,1,2,3,4,5,6
    

    However, I still get TLE for the 5000 to 1 test case. Notice that the algo is O(n) time for this special case. Does it make any sense to further optimize this algo? No. In my whole life, I never see any case that sorting with linked list and a O(n^2) algorithm should be absolutely enough.


Log in to reply
 

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