eine verkettete rekursiv reversed

Question

meine verkettete reverse-funktion gibt das richtige ergebnis. aber ich bin
verwirrt.

linked list= 12->5->4->3 

as per my reverse function the result should be 
4->5->12 

but fortunately it produces the correct reversed list 
3->4->5->12. 

pls help me to understand what happening 




//head_ref global variable 



struct n* reverse(struct n *head){ 

    struct n *pre,*cur; //temp variable for first and second node 

    if(head->next==NULL){ 
     head_ref = head; // head_ref global variable initialized with head pointer 
     return; 
    } 
    pre = head; 
    cur = head->next; 
    reverse(cur); 

    cur->next = pre ; 
    pre->next = NULL; 

} 

ersten Anruf pre = 12 cur = 5 zweiten Anruf pre = 5 cur = 4 3. Aufruf pre = 4 cur = 3

3->next = NULL //base condition fullfilled 
    so it will exit (3rd call) 

    reverse will start from 
    second call 
     pre = 5 
     cur = 4 

meine umgekehrt verknüpft Liste sollte 4-> 5-> 12

sein, aber es produziert 3-> 4-> 5-> 12 (korrekte umgekehrte verkettete Liste)

warum es das korrekte Ergebnis gibt. Bitte erklären ????

Answer 1

uns Lassen Beginnen Sie mit der verknüpften Liste 12->5->4->3. Wenn Ihre Hauptfunktion (oder eine andere aufrufende Funktion) die umgekehrte Funktion aufruft, hat head die Daten 12. Nachfolgend ist der Stapel, der nach dem vierten Aufruf der Umkehrfunktion erstellt wurde.

    |           | 
       |___________________________________________|  gonna be 
       |__*head=3 *head->next=NULL__head_ref=3_____| => popped out 
       |__*head=4 pre=4 curr=3_____________________| 
       |__*head=5 pre=5 cur=4______________________| 
    main calls=>|__*head=12_pre=12 cur=5____________________| 

Wie Sie gesagt haben, sind Sie bereits mit der obigen Abbildung klar. Wenn wir head-> next = NULL haben, wird der oberste Eintrag im Stapel ausgeklappt und der mit * head = 4, pre = 4 und curr = 3 wird zum obersten Eintrag im Stack. Dann berechnet curr-> prev 3-> next = 4 und 4-> next-> NULL.

    |              | 
       |              | 
    popped out=> |______________________________________________________| 
       |__*head=4 pre=4 curr=3__(3->next)=4__(4->next)=NULL___| 
       |__*head=5 pre=5 cur=4_________________________________| 
       |__*head=12_pre=12 cur=5_______________________________| 

Dann Eintrag mit * head = 4 pre = 4 curr = 3 __ (3-> next) = 4 __ (4-> next) = NULL herausspringt, und das gleiche passiert.

In dem verbleibenden Eintrag sehen Sie 12-> next wird NULL, also wird 12 nun zum Tail der verketteten Liste.

    |              | 
       |              | 
       |              | 
       |              | 
    popped out=> |______________________________________________________| 
       |__*head=12_pre=12 cur=5__(5->next)=12_(12->next)=NULL_| 


       |              | 
       |              | 
       |              | 
       |              | 
       |              | 
    popped out=> |______________________________________________________| 

Stapel leer werden und Ihre endgültige verknüpfte Liste hat 3 als Kopf und 12 als Schwanz: 3->4->5->12

Answer 2

3-> next = NULL // Grundbedingung erfüllt, so dass es (3 call)

Rückwärts verlassen wird aus zweiten Anruf starten pre = 5 cur = 4

kein Rückwärts starten von hier

Aufruf pre = 4 cur = 3

Sie umkehren nennen (3), die nichts tun, und Sie Linien

cur->next = pre ; 
pre->next = NULL; 

ausführen, wo cur = 3 und pre = 4, so dass Sie bekam 3-> 4