TLE for mergesort in Python


  • 0
    M
    def mergesort(head):
    if head==None or head.next==None:
        return head
    right=head
    mid=head
    while right.next!=None and right.next.next!=None:
        right=right.next.next
        mid=mid.next
    right=mid.next
    mid.next=None
    return merge(mergesort(head),mergesort(right))
    
    def merge(left,right):  
    nullhead=ListNode(0)
    tail=nullhead
    while left!=None and right!=None:  
        if left.val<=right.val:
            tail.next=ListNode(left.val)
            left=left.next
        else:  
            tail.next=ListNode(right.val)
            right=right.next
        tail=tail.next
    if left==None:
        tail.next=right
    else:
        tail.next=left
    return nullhead.next  
    

    I could not find any problem in my code. Could anyone help me solve the TLE? Thank you :)


  • 0
    C

    This part:
    while right.next!=None and right.next.next!=None:
    right=right.next.next
    mid=mid.next

    needs traverse, so it will take O(n) time every time you call this recursive function, it's different when compared with single list (like [1,4,2,5,6]) merge sort.


Log in to reply
 

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