How to improve O(n^2) python algorithm to ac

  • 0

    I have implemented a typical O(n^2) insertion sort for this problem, however I got TLE on large inputs, when I tried the large input on my desktop, the result is correct. So I am wondering how can I improve the O(n^2) algorithm so that it meets OJ's timing threshold.

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head: return None        # no node
        if not return head   # only 1 node
        if not hasattr(head, "next"): return None   # head is not a ListNode
        # consider head as the last element of the sorted list
        last = head
        # we start from
        curr =
        while curr:
            # if > last, it means is sorted as well
            if curr.val >= last.val:
                last = curr
                curr =
            # start from insert_loc = head, if insert_loc >= curr, insert it
            insert_loc = head
            insert_loc_previous = None
            # find the location to insert
            while curr.val > insert_loc.val and insert_loc_previous != last:
                insert_loc_previous = insert_loc    # pointer to the previous
                insert_loc =
            if not insert_loc_previous:         # insert_loc is head
                temp =
       = head
                head = curr
       = temp
            else:                   # insert in the middle of the sorted list
                temp =
       = insert_loc
       = curr
       = temp
            curr =
        return head

  • 0

    I used python and got an AC. For my code, I pre-processed the list to check whether it is sorted, which kinda of avoiding the worst case.

Log in to reply

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