Рекурсивная инверсия односвязного списка

Question

У меня есть следующий короткий код, который является решением проблемы обращения к связанному списку.

void backwardslist(atom** head) { 
atom* first; 
atom* second; 

if (*head == NULL) return; //if list is empty 

first = *head; 
second = first->next; // intuitive 

if (second == NULL) return; 

backwardslist(&second); // recursive call with 2nd one as head, after we got variables 
        first and second 

first->next->next = first; // when we get to the end, we rearrange it 
first->next = NULL; // so last one is pointing to first, first is pointing to NULL 

*head = second; // I dont understand this part, so the head is changing from the last, 
        to the second element as the recursion goes to the beginning or am i 
        missing something? 

}

не второй = (указатель на второй из двух указателей в рекурсии)?

поэтому первый раз, я понимаю, он должен указывать на последний,

но рекурсия строит назад, его постоянно меняется * голова на второй.

Что находится во втором атме, которое используется?

Спасибо ребята

Answer 1

простой ответ, который приходит на ум это рекурсивный вызов вашей функции до конца не будет достигнута. Затем верните последний узел. Когда возвращается рекурсивная функция, установите следующий указатель узла, возвращаемого головному узлу.

1) A->B->C->D 
    2) A->B->C->D->C 
    3) A->B->C->D->C->B 
    4) A->B->C->D->C->B->A 
    5)   D->C->B->A->Null 

Answer 2

void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest;

/* empty list */ 
if (*head_ref == NULL) 
    return; 

/* suppose first = {1, 2, 3}, rest = {2, 3} */ 
first = *head_ref; 
rest = first->next; 

/* List has only one node */ 
if (rest == NULL) 
    return; 

/* reverse the rest list and put the first element at the end */ 
recursiveReverse(&rest); 
first->next->next = first; 

/* tricky step -- see the diagram */ 
first->next = NULL;   

/* fix the head pointer */ 
*head_ref = rest;    

}