My bottom-up merge sort, I think it's too much for a interview.


  • 0
    M
    class Solution {
    private:
    ListNode* merge(ListNode* slow, ListNode* fast) {
            ListNode dummy(0);
            ListNode* curr = &dummy;
            
            while (slow != NULL && fast != NULL) {
                if (slow->val <= fast->val) {
                    curr->next = slow;
                    curr = slow;
                    slow = slow->next;
                } else {
                    curr->next = fast;
                    curr = fast;
                    fast = fast->next;
                }
            }
            if (slow != NULL) {
                curr->next = slow;
            }
            if (fast != NULL) {
                curr->next = fast;
            }
            return dummy.next;
        }
        
        ListNode* getListTail(ListNode* node, int k) {
            for (int i = 0; node->next != NULL && i < k; ++i) {
                node = node->next;
            }
            return node;
        }
    
    public:
        ListNode* sortList(ListNode* head) {
            int len = 1;
            bool merged = true;
            while (merged) {
                ListNode* nextPair = head;
                ListNode* mergedList = NULL;
                ListNode* prevTail = NULL;
                ListNode* newHead = NULL;
                
                merged = false;
                
                while (nextPair != NULL) {
                    ListNode* secondList = nextPair, *firstList = nextPair;
                    ListNode* tail;
                    
                    // find the tail of the first list to merge.
                    tail = getListTail(firstList, len - 1);
                    if (tail->next != NULL) {
                        secondList = tail->next;
                        tail->next = NULL;
                        
                        // find the tail of the second list
                        tail = getListTail(secondList, len - 1);
                        
                        nextPair = tail->next;
                        tail->next = NULL;
                        
                        merged = true;
                        
                        mergedList = merge(firstList, secondList);
                    } else {
                        mergedList = firstList;
                        nextPair = NULL;
                    }
                    
                    if (newHead == NULL) newHead = mergedList;
                    
                    if (prevTail != NULL) {
                        prevTail->next = mergedList;
                    } else {
                        prevTail = mergedList;
                    }
                    
                    while (prevTail->next != NULL) {
                        prevTail = prevTail->next;
                    }
                }
                
                if (newHead != NULL) head = newHead;
                len = len << 1;
            }
          };
          
            return head;
        }
    

Log in to reply
 

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