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

• Here is my code:

``````def insertionSortList(head):
dummy = ListNode(0)
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.

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