Run time error in SortList


  • 1
    N

    Function mergesort() is recursive, and merge() function link two parts together.

     class Solution {
        public:
            ListNode *sortList(ListNode *head) {
                int length=0;
        
                ListNode* begin=head;
                while(head){
                    head=head->next;
                    length++;
                }
                ListNode *r=mergesort(begin,length);
                return r;
            }
            ListNode *mergesort(ListNode *h, int l){
                if(h==NULL || h->next==NULL) return h;
                ListNode *pre=h;
                ListNode *post;
                int i=0;
                while(i<l/2-1){
                    pre=pre->next;
                    i++;
                }
                post=pre->next;
                pre->next=NULL;
                pre=h;
                ListNode *low=mergesort(pre,l/2);
                ListNode *high=mergesort(post,l-l/2);
                ListNode *result=merge(low,high);
                return result;
            }
        
            ListNode *merge(ListNode *first,ListNode *second){
                ListNode *dummy;
                ListNode *it1=first;
                ListNode *it2=second;
                ListNode *it=dummy;
                while(it1 && it2){
                    if(it1->val<it2->val){
                        it->next=it1;
                        it=it->next;
                        it1=it1->next;
        
                    }
                    else{
                        it->next=it2;
                        it=it->next;
                        it2=it2->next;
        
                    }
        
                }
        
                if(it) it->next=it1;
                if(it2) it->next=it2;
                return dummy->next;
            }
        
        
        };

  • 3
    V

    In he above program dummy is a pointer to ListNode and that node is not initialised hence it is causing run time error. Need to made the modification in line 33 of the program to

    **ListNode dummy = (ListNode )malloc(sizeof(ListNode));

    class Solution {
        public:
            ListNode *sortList(ListNode *head) {
                int length=0;
    
                ListNode* begin=head;
                while(head){
                    head=head->next;
                    length++;
                }
                ListNode *r=mergesort(begin,length);
                return r;
            }
            ListNode *mergesort(ListNode *h, int l){
                if(h==NULL || h->next==NULL) return h;
                ListNode *pre=h;
                ListNode *post;
                int i=0;
                while(i<l/2-1){
                    pre=pre->next;
                    i++;
                }
                post=pre->next;
                pre->next=NULL;
                pre=h;
                ListNode *low=mergesort(pre,l/2);
                ListNode *high=mergesort(post,l-l/2);
                ListNode *result=merge(low,high);
                return result;
            }
    
            ListNode *merge(ListNode *first,ListNode *second){
                ListNode *dummy =  (ListNode *)malloc(sizeof(ListNode));
                ListNode *it1=first;
                ListNode *it2=second;
                ListNode *it=dummy;
                while(it1 && it2){
                    if(it1->val<it2->val){
                        it->next=it1;
                        it=it->next;
                        it1=it1->next;
    
                    }
                    else{
                        it->next=it2;
                        it=it->next;
                        it2=it2->next;
    
                    }
    
                }
    
                if(it) it->next=it1;
                if(it2) it->next=it2;
                return dummy->next;
            }
    
    
        };

Log in to reply
 

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