CODEWITHSUNDEEP
c++linked-list
Ravish Kumar
Ravish Kumar

Reputation: 3

Segmentation Fault Linked List Merge Sort

I am trying to sort linked list using merge sort but every time i get a segmentation fault i have been trying very hard from 2 days and ran debugger many times please some one help . I followed approach of dividing the linked list into 2 parts and recursively calling merge sort .

void merge_sort(Node**head){
    if((*head)->next == NULL){
        return ;
    }
    Node *a , *b ;
    FrontBackSplit( *head, &a, &b);
    merge_sort(&a);
    merge_sort(&b);
    *head = merge(a,b);
}
Node *merge(Node *a , Node*b){
    Node *result = NULL ;
    if(a == NULL){
        return b;
    }
    else if(b == NULL){
        return a;
    }
        if(a->data <= b->data){
            result = a;
            result->next = merge(a ->next,b) ;
        }
        else {
            result = b; 
            result->next = merge(a , b->next) ;
        }
    
    return result ;
}

void FrontBackSplit(Node* source,
                    Node** frontRef, Node** backRef)
{
    Node* fast;
    Node* slow;
    slow = source;
    fast = source->next;
 
    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
 
    /* 'slow' is before the midpoint in the list, so split it in two
    at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

Upvotes: 0

Views: 85

Answers (2)

parsaespro
parsaespro

Reputation: 26

You should also consider the condition in which your head pointer itself is pointing to the null(In case the length is 0)(not just "head -> next " pointer). And then your first if would be like this:

void merge_sort(Node**head){
if((*head)->next == NULL || (*head) == NULL ){
    return ;
}
Node *a , *b ;
FrontBackSplit( *head, &a, &b);
merge_sort(&a);
merge_sort(&b);
*head = merge(a,b);

} `

Upvotes: 1

Afshin
Afshin

Reputation: 9173

You need to debug more, but your code will create segmentation fault if both a and b become NULL in merge() method.

This happens because when both a and b are NULL, you will return NULL, then you *head becomes NULL and any access like (*head)->next will create segmentation fault.

Upvotes: 0

Related Questions