I cannot figure out what's wrong with my code. Please help!


  • 0
    M

    Hi there,

    My code gets TLE when the test data is large, but works fine with small data. When testing on my own machine, the code seems to trap into some infinite loop (it does not terminate when test data is large). But since the code is recursive, it is hard for me to figure out what's going wrong.

    What's interesting is, when I change the code from using mid->next as the end point of the left half to set mid->next = NULL and use NULL as the end point of the left half (unlink the left half and right half), the code got accepted (and even beats 95.5% C++). But I am really curious why my previous code does not work. Please help.

    My original erroneous code:

    class Solution {
        ListNode* sortList(ListNode* begin, ListNode* end) {
            if (begin->next == end) return begin;
            ListNode *head, *mid, *tail;
            head = mid = tail = begin;
            while (tail != end && tail->next != end && tail->next->next != end) {
                tail = tail->next->next;
                mid = mid->next;
            }
            ListNode * first = sortList(begin, mid->next);
            ListNode * second = sortList(mid->next, end);
            ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
            while (first != mid->next && second != end) {
                if (first->val < second->val) {
                    tmpHeadPtr->next = first;
                    first = first->next;
                } else {
                    tmpHeadPtr->next = second;
                    second = second->next;
                }
                tmpHeadPtr = tmpHeadPtr->next;
            }
            if (first != mid->next) {
                tmpHeadPtr->next = first;
                while (first->next != mid->next) {
                    first = first->next;
                }
                first->next = end;
            } else {
                tmpHeadPtr->next = second;
            }
            
            return tmpHead.next;
        }
    public:
        ListNode* sortList(ListNode* head) {
            if (head == NULL) return NULL;
            return sortList(head, NULL);
        }
    };
    

    My "better than 95.5% C++" code

    class Solution {
    public:
    
        ListNode* sortList(ListNode* begin) {
            if (begin == NULL) return NULL;
            if (begin->next == NULL) return begin;
            ListNode *head, *mid, *tail;
            head = mid = tail = begin;
            while (tail != NULL && tail->next != NULL && tail->next->next != NULL) {
                tail = tail->next->next;
                mid = mid->next;
            }
            auto tmp = mid->next;
            mid->next = NULL;
            ListNode * first = sortList(begin);
            ListNode * second = sortList(tmp);
            ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
            while (first != NULL && second != NULL) {
                if (first->val < second->val) {
                    tmpHeadPtr->next = first;
                    first = first->next;
                } else {
                    tmpHeadPtr->next = second;
                    second = second->next;
                }
                tmpHeadPtr = tmpHeadPtr->next;
            }
            if (first != NULL) {
                tmpHeadPtr->next = first;
            } else {
                tmpHeadPtr->next = second;
            }
            
            return tmpHead.next;
        }
    };

  • 0
    M

    I figured it out. It is because I always check first against mid->next, but actually mid->next may be changed when sorting the second half. Therefore, the loop will never end. In order to make the original code work, just use another variable to save the value of mid->next before passing it to sort.

    The corrected code:

    class Solution {
        ListNode* sortList(ListNode* begin, ListNode* end) {
            if (begin->next == end) return begin;
            ListNode *head, *mid, *tail;
            head = mid = tail = begin;
            while (tail != end && tail->next != end && tail->next->next != end) {
                tail = tail->next->next;
                mid = mid->next;
            }
            auto fend = mid->next; // use fend instead of mid->next, since mid->next can change
            ListNode * first = sortList(begin, fend);
            ListNode * second = sortList(fend, end);
            ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
            while (first != fend && second != end) {
                if (first->val < second->val) {
                    tmpHeadPtr->next = first;
                    first = first->next;
                } else {
                    tmpHeadPtr->next = second;
                    second = second->next;
                }
                tmpHeadPtr = tmpHeadPtr->next;
            }
            if (first != fend) {
                tmpHeadPtr->next = first;
                while (first->next != fend) {
                    first = first->next;
                }
                first->next = end;
            } else {
                tmpHeadPtr->next = second;
            }
            
            return tmpHead.next;
        }
    public:
        ListNode* sortList(ListNode* head) {
            if (head == NULL) return NULL;
            return sortList(head, NULL);
        }
    };
    

    Interestingly, this solution is slower than the solution I posted in the question.


Log in to reply
 

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