I tested my solution below locally using python 2.7 and it seems working fine. However, OJ is giving me a TLE on my solution. The thing is: OJ doesn't tell me which input list is causing the TLE error, and I have no way to debug it locally.
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a ListNode def insertionSortList(self, head): newHead = newTail = None while head: cur = head prev = None minNode = head minPrev = None # Find the minimum node in the list while cur: if cur.val < minNode.val: minNode = cur minPrev = prev prev = cur cur = cur.next # remove the minimum node from list and append it to the # new list if minPrev: minPrev.next = minNode.next else: head = minNode.next minNode.next = None if newHead is None: newHead = minNode newTail = minNode else: newTail.next = minNode newTail = minNode return newHead