Why this recursive merge sort got TLE for test case [2, 1]


  • 0
    I
    class Solution {
    public:
        ListNode *mergeSort(ListNode *head, int len) {
            // if only less than two nodes left
            if (len < 2) {
                return head;
            }
    
            // divide it into two parts
            ListNode *leftHead = head, *rightHead = head;
            int leftLen = len >> 1;
            int rightLen = len - leftLen;
    
            for (int i = 0; i < leftLen; ++i) {
                rightHead = rightHead->next;
            }
    
            // sort the left
            leftHead = mergeSort(leftHead, leftLen);
            // sort the right
            rightHead = mergeSort(rightHead, rightLen);
    
            // merge back
            ListNode dummyNode(0);
            head = &dummyNode;
            while (leftLen > 0 && rightLen > 0) {
                if (leftHead->val < rightHead->val) {
                    head->next = leftHead;
                    leftHead = leftHead->next;
                    --leftLen;
                } else {
                    head->next = rightHead;
                    rightHead = rightHead->next;
                    --rightLen;
                }
                head = head->next;
            }
    
            head->next = leftLen > 0 ? leftHead : rightHead;
            
            return dummyNode.next;
        }
    
        ListNode *sortList(ListNode *head) {
            // get the list length
            int listLen = 0;
            ListNode *newHead = head;
            while (newHead != NULL) {
                ++listLen;
                newHead = newHead->next;
            }
    
            newHead = mergeSort(head, listLen);
            return newHead;
        }
    };

  • 1
    J

    The last node is not point to NULL. So the link list has a cycle. This will lead to endless loop when testing ! ! !
    For example, the test case is 2->1->NULL, but your method leads to 2->1->2......


  • 0
    I

    cool, wasn't aware of that. Thnx.


Log in to reply
 

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