# Definition for singlylinked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
min_node = ListNode(1)
min_node.next = head
node = head
while node.next:
root = min_node
while root != node and root.next.val < node.next.val:
root = root.next
if root != node:
temp = node.next
node.next = node.next.next
temp.next = root.next
root.next = temp
else:
node = node.next
return min_node.next
Why did I get a TLE? it is supposed to be O(n^2)


The reason of Time Limit Exceeded is that this is a loop in your submitted linkedlist.
class Solution(object):
def insertionSortList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return None min_node = ListNode(1) min_node.next = None # head.next = None node = head while node: pre = min_node root = min_node.next while root != None and root.val < node.val: pre = root root = root.next pre.next = node temp = node.next node.next = root node = temp return min_node.next