One way to accept in python against TLE


  • 6
    I

    My original code is very intuitive. I checked each unsorted element one by one and added it into sorted part. The way I added it is that I check from the head to tailer of the sorted part. Here is my original code in python and off-line test for 2000 data costs 2.3s while the result is TLE for on-line test.

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        linkHead = ListNode(0)
        linkHead.next = head
        sortedEnd = linkHead.next
    
        if sortedEnd == None:
            return head
     
        while sortedEnd.next != None:
            pointer = sortedEnd.next
            sortedEnd.next = pointer.next
    
            innerPointer = linkHead
    
            while innerPointer != sortedEnd and innerPointer.next.val < pointer.val:
                innerPointer = innerPointer.next
                
            pointer.next = innerPointer.next
            innerPointer.next = pointer
    
            if innerPointer == sortedEnd:
                sortedEnd = pointer
                
        return linkHead.next
    

    Then I change the way to find the insertion spot like this:
    The off-line test costs 1.7s and it accepted for on-line test

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        linkHead = ListNode(0)
        linkHead.next = head
        sortedEnd = linkHead.next
    
        if sortedEnd == None:
            return head
    
        innerPointer = linkHead.next  #declare innerPointer here
    
        while sortedEnd.next != None:
            pointer = sortedEnd.next
            sortedEnd.next = pointer.next
    
            # reset innerPointer only when pointer is needed to be inserted before innerPointer
            if innerPointer.val > pointer.val:
                innerPointer = linkHead
    
            while innerPointer != sortedEnd and innerPointer.next.val < pointer.val:
                innerPointer = innerPointer.next
                
            pointer.next = innerPointer.next
            innerPointer.next = pointer
    
            if innerPointer == sortedEnd:
                sortedEnd = pointer
                
        return linkHead.next
    

    There are some other method to improve performance, e.g. section the linkList and store the value of each segment's front elem, then the process of finding the insertion spot will be more efficient


  • 0
    S

    pretty helpful! the innerPointer help me to import runtime from 4.5s to 1.5s for the longest test case.
    Thx!


  • 12
    S

    I experienced the same process, and eventually got the code below:

    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def insertionSortList(self, head):
            pre = cursor = dummy_head = ListNode(0)
            dummy_head.next = head
        
            while cursor.next:
                if pre.next.val > cursor.next.val:
                    pre = dummy_head
            
                while pre.next.val < cursor.next.val:
                    pre = pre.next
                
                if pre != cursor:
                    node = cursor.next
                    cursor.next = node.next
                    node.next = pre.next
                    pre.next = node
                else:
                    cursor = cursor.next
        
            return dummy_head.next
    

    One thing to note here though: the output message was kinda misleading by saying the last executed input was [5000, 4900, ..., 1]. The improvement above doesn't help on this case; actually it adds one more unnecessary check for pre.next.val > cursor.next.val. But it will help a lot on the case [1, 2, ..., 500], if it exists. Without the trick, it costs 2s+, while the trick brings the running time down to 3ms+.

    Without the trick: 1 loops, best of 3: 2.34 s per loop

    With the trick: 100 loops, best of 3: 3.11 ms per loop

    If I have to guess, OJ measures the overall running time on all the test cases, and it exceeds the total limit while running [5000, 4999, ..., 1] after finishing [1, 2, ..., 5000].


  • 0
    S

    I think you were referring to skip list.


  • 0
    B

    I don;t understand the purpose of pre and why you always compare .next other than pre/cursor itself?


  • 0
    I

    When we find a node that should be moved to a place prior to it, we will need to know its predecessor node so we can connect its predecessor and successor after moving the node. For example, given the case 2 -> 1 -> 3, when we move 1 to the beginning, we will need to connect 2 with 3; in this code, cursor will be on 2, so it's easy to connect 2 with 3. Similar strategy applies to pre.


Log in to reply
 

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