обратный связанный список рекурсивно

Question

моя функция обратной связи связанного списка дает правильный результат. но я
смущенный.

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; 

} 

первый вызов до = 12 дворняжки = 5 второго вызова предварительно = 5 дворняжки = 4 третьего вызова предварительно = 4 дворняжки = 3

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

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

моего обращенный связана список должен быть 4-> 5-> 12

, но он производит 3-> 4-> 5-> 12 (правильный перевернутый список)

Почему он дает правильный результат. PLS объяснить ????

Answer 1

Давайте начать со связанного списка 12->5->4->3. Когда ваша основная (или другая вызывающая функция) вызывает обратную функцию, голова имеет данные 12. Далее следует стек, созданный после четвертого вызова функции обратного вызова.

    |           | 
       |___________________________________________|  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____________________| 

Как вы уже сказали, вы уже поняли приведенную выше фигуру. Когда у нас есть head-> next = NULL, появляется самая верхняя запись в стеке, а первая с * head = 4, pre = 4 и curr = 3 становится самой верхней записью в стеке. Тогда curr-> prev оценивает до 3-> next = 4 и 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_______________________________| 

Тогда запись с * = 4 головки до 4 = CURR = 3 __ (3-> следующая) = 4 __ (4-> следующая) = NULL, выскакивает и то же самое происходит.

    |              | 
       |              | 
       |              | 
    popped out=> |______________________________________________________| 
       |__*head=5 pre=5 cur=4____(4->next)=5___(5->next=NULL)_| 
       |__*head=12_pre=12 cur=5_______________________________| 

В оставшейся одной записи, которую вы можете увидеть 12-> следующая становится NULL, поэтому 12 теперь становится хвост связного списка.

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


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

Стек становится пустым и окончательный связанный список имеет 3 в качестве главы и 12, как хвост: 3->4->5->12

Answer 2

3-> следующий = NULL, // база условия fullfilled поэтому он будет выходить (3-й вызова)

реверса начнет со второго вызова предварительно = 5 CUR = 4

нет обратного старта здесь

вызов предварительно = 4 дворняжка = 3

вы называете обратный (3), которые ничего не делают, и вы выполняете строки

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

где дворняжка = 3 и до = 4, так что вы получили 3-> 4