# Python time limit is too tight

• I have basically the same code in python and java (see below). python got TLE, but java was accepted. I propose to relax the python time limit a little bit.

Python

``````class Solution:
# @return a ListNode
srt = None
node.next = None
srt = self.insertTo(srt, node)
return srt

while node.next and node.val > node.next.val:
node.val, node.next.val = node.next.val, node.val
node = node.next
``````

java

``````public class Solution {
ListNode srt = null;
node.next = null;
srt = insertTo(srt, node);
}
return srt;
}

public ListNode insertTo(ListNode head, ListNode node) {
while (node.next != null && node.val > node.next.val) {
node.val = node.val ^ node.next.val;
node.next.val = node.val ^ node.next.val;
node.val = node.val ^ node.next.val;
node = node.next;
}
}
}``````

• Almost one year later, python still couldn't pass the 1 to 5000 case.

• Try sorting the nodes not the values inside nodes, I'm not sure if it'll help, but worth a try.

• This implementation definitely will not get accepted. You did not use the O(1) insertion and deletion property of a linked-list. The other TLE solutions do not have this kind of problem and they just need a lit bit optimization because they do not really really understand the classical code of insertion sort.

• @sheehan Ahh why did I not have such problem and get passed pretty easy?

``````class Solution(object):
"""
:rtype: ListNode
"""
dummy = ListNode(-1)
while p:
q = dummy
next = p.next
if p.val < pre.val:
while q.next and q.next != p:
if q.next.val >= p.val:
pre.next = p.next
q.next, p.next = p, q.next
break
q = q.next
else:
pre = p
p = next
return dummy.next
``````

• @yintaosong still getting TLE in last case.

• AC code~~

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
dummy = ListNode(-1)
while current:
print(current.val)
begin = dummy
current_next = current.next
if current_next and current_next.val < current.val:
tmp_current = current
current.next = current_next.next
while begin != tmp_current:
if begin.next.val > current_next.val:
current_next.next = begin.next
begin.next = current_next
break
else:
begin = begin.next
else:
current = current.next
return dummy.next
``````

• By default, this question is only ask to implement the insertion sort , which should acceptable with O(N^2) time complexity.
this is the code I have , which should be O(N^2)
"""
class Solution(object):
def insert(self,node,ls):
if not ls:
return node
if node.val <= ls.val:
node.next = ls
return node
ls.next = self.insert(node,ls.next)
return ls

``````def insertionSortList(self, head):
'''
:rtype: ListNode
'''
return None