SortList Python TLE


  • 0
    L

    I think the following code is O(nlogn), however the system keep throwing TLE for large input.

    class Solution:
        def merge(self, left, right):
            head = ListNode(0)
            curr = head
            while left != None and right != None:
                if left.val <= right.val:
                    v = left
                    left = left.next
                else:
                    v = right
                    right = right.next
    
                curr.next = v
                curr = curr.next
    
            while left != None:
                curr.next = left
                left = left.next
                curr = curr.next
    
            while right != None:
                curr.next =right 
                right = right.next
                curr = curr.next
    
    
            curr.next = None
            return head.next
    
        # @param head, a ListNode
        # @return a ListNode
        def sortList(self, head):
            if head == None or head.next == None:
                return head
    
            left = head
            right = head
            while right.next != None and right.next.next != None:
                left = left.next
                right = right.next.next
    
            right = left.next
            left.next = None
            left = head
    
            left = self.sortList(left)
            right = self.sortList(right)
    
            return self.merge(left, right)

  • 0
    J

    I think it will be better if you replace the last two while loop of merge() with if ,which is as follows,

     def merge(self, left, right):
            head = ListNode(0)
            curr = head
            while left != None and right != None:
                if left.val <= right.val:
                    curr.next = left
                    left = left.next
                else:
                    curr.next = right
                    right = right.next
                
                curr = curr.next
            if left != None:
                curr.next = left
    
            if right != None:
                curr.next = right 
    
            return head.next

  • 0
    M

    Hi, Joe! My situation is similar to lennydizzy. I did as you suggested, but I still got TLE. Are you sure it's a major factor?


Log in to reply
 

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