分段故障链表合并排序

Question

我正在尝试使用合并排序对链表进行排序，但每次我遇到分段错误时，我从2天开始就一直在努力尝试，并多次运行调试器，请帮帮忙。我遵循了将链表分成两部分并递归调用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;
}

Answer 1

您还应该考虑头指针本身指向null的情况(如果长度为0)(而不仅仅是"head -> next“指针)。然后你的第一个if会是这样的：

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

}`

Answer 2

您需要进行更多的调试，但是如果a和b都成为merge()方法中的NULL，那么您的代码将会产生分段错误。

这是因为当a和b都是NULL时，你将返回NULL，然后你的*head变成NULL，任何像(*head)->next这样的访问都会产生分段错误。