TLE for Python?


  • 3
    I

    I have a Time Limit Exceeded when input a list of 5000 numbers.

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertSort(self, head):
        if head==None or head.next==None:
            return head
        self.insertSort(head.next)
        l=head
        r=head.next
        while r!=None:
            if l.val>r.val:
                l.val,r.val=r.val,l.val
                l=r
                r=r.next
            else:
                return head
        return head
    def insertionSortList(self, head):
        return self.insertSort(head)
    

    is there any solution for the problem?


  • 14
    U

    Your recursive code possibly incurs extra comparison and value swap steps. My iterate version without value swap operation is accepted.

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head:
            return head
        fh = ListNode(0)
        fh.next = head
        cur = head
        while cur.next:
            if cur.next.val < cur.val:
                pre = fh
                while pre.next.val < cur.next.val:
                    pre = pre.next
                t = cur.next
                cur.next = t.next
                t.next = pre.next
                pre.next = t
            else:
                cur = cur.next
        return fh.next

  • 0
    L

    First, it's a good recursive method for the question. The TLE maybe caused by the maximum recursion depth exceeded in python.
    You can test your code in you own computer, and this will cause a RuntimeError:maximum recursion depth exceeded in cmp


  • 0
    C

    Same idea as us917, just reads slightly different:

    def insertionSortList(self, head):
        if head is None or head.next is None:
            return head
        to_insert_after = sentinel = ListNode(0)
        current = sentinel.next = head
        while current.next:
            if current.next.val >= current.val:
                current = current.next
                continue
            to_insert_after = sentinel
            while to_insert_after.next.val < current.next.val:
                to_insert_after = to_insert_after.next
            to_insert = current.next
            current.next = to_insert.next
            to_insert.next = to_insert_after.next
            to_insert_after.next = to_insert
        return sentinel.next

Log in to reply
 

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