Python time limit is too tight


  • 16
    Y

    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:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        srt = None
        while head:
            node = head
            head = head.next
            node.next = None
            srt = self.insertTo(srt, node)
        return srt
        
    def insertTo(self, head, node):
        node.next = head
        head = node
        while node.next and node.val > node.next.val:
            node.val, node.next.val = node.next.val, node.val
            node = node.next
        return head
    

    java

    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            ListNode srt = null;
            while (head != null) {
                ListNode node = head;
                head = head.next;
                node.next = null;
                srt = insertTo(srt, node);
            }
            return srt;
        }
        
        public ListNode insertTo(ListNode head, ListNode node) {
            node.next = head;
            head = 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;
            }
            return head;
        }
    }

  • 0
    S

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


  • 0
    T

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


  • 0
    C

  • 0
    C

  • 0

    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.


  • 0

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

    class Solution(object):
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head:
                dummy = ListNode(-1)
                pre = dummy.next = head
                p = head.next
                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
    

  • 0
    S

    @yintaosong still getting TLE in last case.


  • 0
    L

    AC code~~

    # Definition for singly-linked 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 head is None:
                return head
            dummy = ListNode(-1)
            dummy.next = head
            current = head
            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
    

  • 0
    Z

    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):
        '''
        :type head: ListNode
        :rtype: ListNode
        '''
        if not head:
            return None
        car = head
        cdr = head.next
        car.next = None
        sortedd = self.insertionSortList(cdr)
        return self.insert(car,sortedd)
    

    """


  • 0
    C

    @jedihy because as you said, you optimized the insertion sort. The point is that this problem specifically asks for insertion sort solution, which we all know is not the best optimized solution anyway. so it should accept O(N^2) solutions


Log in to reply
 

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