Wie kann ich die Linkliste, die ich in C

Question

erstellt habe, umkehren? Ich habe eine verkettete Liste erstellt, konnte aber nicht daran denken, sie umzukehren. Ich kenne den Algo, aber ich denke, ich habe einen Fehler bei der Erstellung der Liste gemacht. Was könnte die Umkehrfunktion sein, damit es funktioniert? Im Folgenden finden Sie den Code ein:

typedef struct Node{ 
    int data; 
    struct Node* next; 
} node; 
node* head; 
int count; 
void insertAtBegin(int value){ 
    if(head==NULL){ 
     head = (node*)malloc(sizeof(node)); 
     head->data = 0; 
     head->next = NULL; 
    } 
    node* newNode = (node*)malloc(sizeof(node)); 
    newNode->data = value; 
    newNode->next = head->next; 
    head->next = newNode; 
    count++; 
} 

void display(){ 
    node* temp = (node*)malloc(sizeof(node)); 
    temp = head; 
    while(temp->next!=NULL){ 
     printf("%d\t",temp->next->data); 
     temp = temp->next; 
    } 
    printf("\n"); 
} 

void reverse(){ 
    node *p, *q, *r; 

    p = q = r = head; 
    p = p->next->next; 
    q = q->next; 
    r->next = NULL; 
    q->next = r; 

    while (p != NULL){ 
     r = q; 
     q = p; 
     p = p->next; 
     q->next = r; 
    } 
    head = q; 
} 

void main(){ 
    insertAtBegin(5); 
    insertAtBegin(6); 
    display(); 
    reverse(); 
    display(); 
    printf("\nSize of linked list is %d",count); 
} 

Answer 1

Angenommen, Sie haben die folgende Liste haben:

head = n0 
n0 -> ... -> A -> B -> C -> D -> E -> ... -> nN -> NULL 

Dass Sie umkehren wollen: Jetzt

head = nN 
nN -> ... -> E -> D -> C -> B -> A -> ... -> n0 -> NULL 

, lassen Sie uns den Fall betrachten, wenn die Der Anfang der Liste ist bereits umgekehrt und Sie haben mit dem Knoten C zu tun. Ihre Liste zu diesem Zeitpunkt:

head = B 
B -> A -> ... -> n0-> NULL 
tmpHead = C 
C -> D -> E ... -> nN -> NULL 

Wo tmpHead eine temporäre Variable ist, die Ihnen erlauben keinen Verweis auf C zu verlieren (wie B.next jetzt zeigt auf A) Sie möchten:

1. connect B-C so dass B kommt nach C
2. Set Kopf C, dem neuen Leiter der umgekehrten Liste
3. halten D in der temporären Variablen tmpHead, so dass Sie es immer noch

dann wird Umkehren zugreifen:

node * tmp = tmpHead.next; // 3. part 1 
tmpHead.next = head;   // 1. 
head   = tmpHead;  // 2. 
tmpHead  = tmp;   // 3. part 2 

Das ist Stop-Zustand der Hand: Sie aufhören müssen, wenn Sie das Ende erreicht der Liste, wenn tmpHeadNULL ist. Bezüglich der Initialisierung, wie head, um auf den umgekehrten Teil und tmpHead auf den nicht umgekehrten Teil zu zeigen. So muss tmpHead auf head und head auf NULL eingestellt werden.

Am Ende erhalten Sie die folgende Funktion, die als Eingangsparameter

void reverse(node ** head) 
{ 
    node * tmpHead = (* head); 
    (* head)  = NULL; 

    while(tmpHead) 
    { 
    node * tmp = tmpHead->next; 
    tmpHead->next = (* head); 
    (* head)  = tmpHead; 
    tmpHead  = tmp; 
    } 
} 

Hinweis, dass es ein „Problem“ ist man sich einen neuen Knoten einfügen mit der Art und Weise einen Zeiger auf den ersten Knoten der Liste nehmen Der Anfang Ihrer Liste: Sie behalten immer einen "Phantom" -Knoten mit Daten auf 0 und Sie rufen head. Also, der erste echte Knoten der Liste, wie ich es definiert habe, ist head->next. Das heißt, Sie müssen die reverse Funktion wie folgt aufrufen: reverse(& (head->next)) oder die Funktion etwas ändern.

Bitte beachten Sie auch, dass Sie das Ergebnis eines malloc nicht werfen sollten. Do I cast the result of malloc?