Why my python code time limited exceeded (MergeSort)


  • 0
    M

    I just modify the pseudo code in the book Introduction to Algorithms. In merge function, I want merge all the nodes from preNode (whose location is A[start - 1] if the data structure is list) to postNode (whose location is A[end + 1]. All nodes in this range has been divided into two sorted linked list, one is from starLNode, another is from starRNode. But why its time limited exceeded? Is my code correct?

    class Solution:
        def sortList(self, head):
            if head == None:
                return None
            if head.next == None:
                return head
            length = 0;
            locNode = head
            while locNode.next != None:
                locNode = locNode.next
                length += 1
            self.sort(head, 1, length)
        
        def sort(self, head, start, end):
            if start < end:
                mid = (start + end) / 2
                self.sort(head, start, mid)
                self.sort(head, mid + 1, end)
                self.merge(head, start, mid, end)
        
        def merge(self, head, start, mid, end):
            nodeScan = head.next
            preNode = head
            for loc in range(1, end + 1):
                if loc == start:
                    startLNode = nodeScan
                if loc == mid + 1:
                    startRNode = nodeScan
                if loc == end:
                    postNode = nodeScan.next
                    
                nodeScan = nodeScan.next
                if loc < start:
                    preNode = preNode.next
                    
            for i in range(0, end - start + 1):
                if startRNode == None:
                    preNode.next = startLNode
                    preNode = preNode.next
                    startLNode = startLNode.next
                elif startLNode.val <= startRNode.val:
                    preNode.next = startLNode
                    preNode = preNode.next
                    startLNode = startLNode.next
                else:
                    preNode.next = startRNode
                    startRNode = startRNode.next
                    preNode = preNode.next
            preNode.next = postNode

Log in to reply
 

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