Segmentierungsfehler beim Finden des mittleren Elements in einer verketteten Liste

Question

Ich versuche das mittlere Element einer verknüpften Liste zu finden, aber ich bekomme einen Segmentierungsfehler, und ich bin mir nicht sicher, was schief läuft. Dies ist meine Implementierung des Hasen Kaninchen-Algorithmus:

//fast slow pointer method 
void ptMiddle(struct node **head_ref) 
{ 
    struct node *fast = (*head_ref); 
    struct node *slow = (*head_ref); 
    fast = fast->next; 

    while(fast!=NULL) 
    { 
     // printf("%d%d",slow->data,fast->data); 
     slow = slow->next; 
     fast = fast->next->next; 
    } 
    printf("Middle elemnet is:%d\n",slow->data); 
} 

int main() 
{ 
    struct node * head=NULL; 
    push(&head,1); 
    push(&head,2); 
    push(&head,3); 
    push(&head,4); 
    printList(&head); 
    printf("M:%d\n",middleNode(&head)->data); 
    printf("here"); 
    append(&head,5); 
    append(&head,6); 
    printList(&head); 
    printf("M:%d\n",middleNode(&head)->data); 
    printf("here"); 
    ptMiddle(&head); 

    return 0; 
} 

Bitte helfen Sie aus.

Answer 1

Ihr Problem ist in der Zeile:

fast = fast->next->next; 

Stellen Sie sich zwei Elemente in der verknüpften Liste haben: A -> B -> NULL, die zuerst von Ihnen starten fast = fast->next Ausführung, die B Knoten in schnellen Zeige führt.

Wenn Sie die While-Schleife eingeben, versuchen Sie, B->next->next zu erhalten, was zu NULL->next führt, was eindeutig nicht existiert.

Die Implementierung ist einfach falsch, Sie sollten diesen Fall vermeiden. Die while könnte geändert werden in:

while(fast!=NULL && fast->next != NULL) 

und das würde es beheben.

Denken Sie daran, dass Sie im Falle eines Paares von Elementen immer das mittlere Element erhalten, das mehr übrig ist. In A -> B -> NULL erhalten Sie Knoten A.