Non recursive mergeSort implementation


  • 0
    Z
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            int interval = 1;
            while(1){
                ListNode *node = head;
                bool UpdateHead = true;
                ListNode *preNode = NULL;
                while(1){
                    ListNode *first_link_head, *first_link_tail, *second_link_head, *second_link_tail;
                    first_link_head=first_link_tail=second_link_head=second_link_tail=node;
                    int cnt = interval;
                    while(second_link_head && cnt--){
                        first_link_tail = second_link_head; 
                        second_link_tail = second_link_head = second_link_head->next;
                    }
                    if(second_link_head){
                        cnt = interval;
                        
                        while(second_link_tail->next && --cnt){
                            second_link_tail = second_link_tail->next; 
                        }
                        
                        ListNode *merge_link, *merge_link_head;
                        merge_link = merge_link_head = NULL;
                        node = second_link_tail->next; 
                        second_link_tail->next = NULL;
                         first_link_tail->next = NULL;
                        while( second_link_head || first_link_head ){
                           if(!second_link_head || first_link_head && second_link_head && first_link_head->val < second_link_head->val){
                               merge_link = !merge_link ? first_link_head : merge_link->next = first_link_head;
                               first_link_head = first_link_head->next;
                           }else{
                               merge_link = !merge_link ? second_link_head : merge_link->next = second_link_head;
                               second_link_head = second_link_head->next;
                           }
                           if(merge_link_head == NULL){
                              merge_link_head = merge_link;  
                           }
                           if(UpdateHead){
                               head = merge_link;
                               UpdateHead = false;
                           }
                        }
                        
                        if(preNode != NULL){
                           preNode->next = merge_link_head;
                        }
                        preNode = merge_link;
                    }else{
                        if(preNode != NULL){
                           preNode->next = node;
                        }
                        break;
                    }    
                }
                if(UpdateHead){
                    break;
                }
                interval *= 2;
            }
            return head;
        }
    };
    

    This is my AC code by using non-recursive merge sort


Log in to reply
 

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