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

• After lots of TLE, I modified the post from jianchao.li.fighter 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:
# @return {ListNode}
while cur:
if cur.next and cur.next.val < cur.val:
while pre.next and pre.next.val < cur.next.val:
pre = pre.next
tmp = pre.next
pre.next = cur.next
cur.next = cur.next.next
pre.next.next = tmp
else:
cur = cur.next
``````

• 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 = cur.next.val
while pre.next and pre.next.val < val:
``````

gets it down to about 345 ms. Doing

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

gets it down to about 310 ms.

• Thank you so much!!

• what is the meaning of cur.next = cur.next.next? thanks

• A-B-C will become A-C

• oh, I got it. Thanks a lot !!

• 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.

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