Relatively short C++ in place merge sort solution non-recursive, constant space


  • 0
    W
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if (!head)
                return NULL;
                
            ListNode dummyPre(0);
            dummyPre.next = head;
            bool shouldContinue = true;
            for (int stepSize = 1; shouldContinue; stepSize *= 2) {
                ListNode* curTail = sortAndCombine(&dummyPre, dummyPre.next, stepSize);
                shouldContinue = (curTail != NULL);
                while (curTail) {
                    curTail = sortAndCombine(curTail, curTail->next, stepSize);
                }
            }
            
            return dummyPre.next;
        }
        
        // precondition: head1 is not NULL
        // returns the last node of the sorted segment
        ListNode* sortAndCombine(ListNode *pre, ListNode *head1, int stepSize)
        {
            if (!head1) {
                return NULL;
            }
        
            ListNode *halfEnd = head1;
            for (int i = 1; i < stepSize; i++) {
                halfEnd = halfEnd->next;
                if (!halfEnd) {
                    return NULL;
                }
            }
        
            ListNode *head2 = halfEnd->next;
            if (!head2) {
                return NULL;
            }
        
            ListNode *preCursor1 = pre;
            ListNode *preCursor2 = halfEnd;
            ListNode *cursor1 = head1;
            ListNode *cursor2 = head2;
            int cursor1Moves = 0;
            int cursor2Moves = 0;
        
            while (cursor2 && cursor1Moves < stepSize && cursor2Moves < stepSize) {
                if (cursor1->val <= cursor2->val) {
                    preCursor1 = cursor1;
                    cursor1 = cursor1->next;
                    cursor1Moves++;
                } else {
                    preCursor1->next = cursor2;
                    preCursor1 = cursor2;
                    ListNode *temp = cursor2->next;
                    cursor2->next = cursor1;
                    preCursor2->next = temp;
                    cursor2 = temp;
                    cursor2Moves++;
                }
            }
        
            ListNode *tail = pre;
            for (int i = 0; i < stepSize * 2 && tail->next; i++) {
                tail = tail->next;
            }
        
            return tail;
        }
    };

Log in to reply
 

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