Python again, how to improve so that run time will be below 500ms?

  • 2

    After lots of TLE, I modified the post from as below, but it still took about 1664ms.

    I saw lots of people were in the "<500ms group", how did you do that!?
    Could someone give me a hint? Thanks a lot!

    class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def insertionSortList(self, head):
    	newhead = ListNode(0) = head
    	pre, cur = newhead, head
    	while cur:
    		if and < cur.val:
    			while and <
    				pre =
    			tmp = = = = tmp
    			pre = newhead
    			cur =

  • 3

    I just submitted yours and it now gets accepted in about 430 ms. Could be the new-style classes LeetCode is using now, see this thread for a small discussion, including speed test results.

    Furthermore, doing

                val =
                while and < val:

    gets it down to about 345 ms. Doing

                val =
                while True:
                    next =
                    if not next or next.val >= val:
                    pre = next

    gets it down to about 310 ms.

  • 0

    Thank you so much!!

  • 0

    what is the meaning of = thanks

  • 0

    A-B-C will become A-C

  • 0

    oh, I got it. Thanks a lot !!

  • 0

    There's a test case that essentially checks if you're doing insertion sort in the classical sense, i.e. from right to left, rather than from left to right.

    That's a bit of a pain with a singly LinkedList (and I don't think it's possible if you want to maintain O(1) space complexity).

    Modifying your code to check if the target value is greater than or equal to the predecessor and to break if so should dramatically improve the performance.

Log in to reply

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