One way to accept in python against TLE
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 t
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.\n\n    class Solution:\n    # @param head, a ListNode\n    # @return a ListNode\n    def insertionSortList(self, head):\n        linkHead = ListNode(0)\n        linkHead.next = head\n        sortedEnd = linkHead.next\n\n        if sortedEnd == None:\n            return head\n     \n        while sortedEnd.next != None:\n            pointer = sortedEnd.next\n            sortedEnd.next = pointer.next\n\n            innerPointer = linkHead\n\n            while innerPointer != sortedEnd and innerPointer.next.val < pointer.val:\n                innerPointer = innerPointer.next\n                \n            pointer.next = innerPointer.next\n            innerPointer.next = pointer\n\n            if innerPointer == sortedEnd:\n                sortedEnd = pointer\n                \n        return linkHead.next\n\nThen I change the way to find the insertion spot like this:\nThe off-line test costs 1.7s and it accepted for on-line test\n\n    class Solution:\n    # @param head, a ListNode\n    # @return a ListNode\n    def insertionSortList(self, head):\n        linkHead = ListNode(0)\n        linkHead.next = head\n        sortedEnd = linkHead.next\n\n        if sortedEnd == None:\n            return head\n\n        innerPointer = linkHead.next  #declare innerPointer here\n\n        while sortedEnd.next != None:\n            pointer = sortedEnd.next\n            sortedEnd.next = pointer.next\n\n            # reset innerPointer only when pointer is needed to be inserted before innerPointer\n            if innerPointer.val > pointer.val:\n                innerPointer = linkHead\n\n            while innerPointer != sortedEnd and innerPointer.next.val < pointer.val:\n                innerPointer = innerPointer.next\n                \n            pointer.next = innerPointer.next\n            innerPointer.next = pointer\n\n            if innerPointer == sortedEnd:\n                sortedEnd = pointer\n                \n        return linkHead.next\n\nThere 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
['Python']