Why get TLE error if I comment out the 3rd to last line??


  • 0
    M
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        
        before = ListNode(0)
        fake = before
        after = ListNode(0)
        after_head = after
        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next
        #after.next = None              if commented out this line, I get TLE!! why??
        before.next = after_head.next
        return fake.next

  • 0
    R

    You get TLE because head.next was not null when you assigned head to after (in the else case of the while loop). This means that after.next is also not null and causes infinite loop.


  • 0
    M

    but "after.next = None" is out side the while loop? why would it cause infinite loop?


  • 0
    R

    Consider the input [2,1], 2. This means that at the beginning you have two nodes in the list:

    head: {val = 2, next = node1}
    node1: {val = 1, next = None}
    

    After the loop you get the following nodes:

    before:  {val = 1, next = None} //this is node1
    after: {val = 2, next = hode1} //this is head
    

    Since node1 == before, this can be rewritten as:

    before:  {val = 1, next = None} //this is node1
    after: {val = 2, next = before} 
    

    Since after_head.next is equal to after, the line

    before.next = after_head.next
    

    changes the state of the nodes to:

    before: {val = 1, next = after}
    after: {val = 2, next = before}
    

    As a result you return a list that contains a cycle and it causes TLE when the judge is trying to verify the answer.


  • 0
    M

    ohh that makes sense! thank you very much!


Log in to reply
 

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