Segmentation Fault Linked List Merge Sort

Question

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;
}

parsaespro · Accepted Answer · 2021-07-06 10:49:34Z

1

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);

} `

answered Jul 6, 2021 at 10:49

parsaespro

261 bronze badge

Sign up to request clarification or add additional context in comments.

4 Comments

Ravish Kumar Over a year ago

Thanks ! The code is running fine now , but on gcc compiler then error still comes :-')

molbdnilo Over a year ago

You need to check *head before (*head)->next.

Ravish Kumar Over a year ago

@molbdnilo Tried that still doesn't work :-')

molbdnilo Over a year ago

I wouldn't rule out that you have a bug in FrontBackSplit, or in the input. Please post a minimal reproducible example.

Afshin · Accepted Answer · 2021-07-06 10:45:53Z

0

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.

answered Jul 6, 2021 at 10:45

Afshin

9,2401 gold badge28 silver badges59 bronze badges

1 Comment

Ravish Kumar Over a year ago

Thanks ! The code is running fine now , but on gcc compiler then error still comes :-')

Collectives™ on Stack Overflow

Segmentation Fault Linked List Merge Sort

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related