Reverse linked list - recursive inversion method

(1) Thought: Contrary to the idea of ​​the iterative inversion method, the realization idea of ​​the recursive inversion method is to start from the tail node of the linked list and traverse forward in turn. The traversal process changes the direction of each node in turn, that is, the otherpoints to the previous node.
(2) Implementation (it is recommended to read the code first, then the diagram to make the understanding more profound):

Start recursion:

New_head comes to the last node of the linked list after three recursive function calls, because new_head=head->next, so head always remains at the previous node of new_head.

When recursing to the last level:

Begin to recurse layer by layer:

End of recursion.

The final result is:

Code snippet:

link* recursive_reverse(link* head) {// out recursive conditionif (head == NULL || head->next == NULL){return head;}else{//new_head always finds the address of the last element in the linked listlink *new_head = recursive_reverse(head->next);//After recursion, put the linked listhead->next->next = head;head->next = NULL;return new_head;}}

Complete code:

#include#includetypedef struct Link{int elem;struct Link* next;}link;link* initLink(){int i;//define the head pointerlink* head=NULL;//define the first nodelink* temp=(link*)malloc(sizeof(link));//Initialize the first nodetemp->elem=1;temp->next=NULL;head=temp;//create other nodesfor(i=2;i<5;i++){link* a=(link*)malloc(sizeof(link));a->elem=i;a->next=NULL;temp->next=a;temp=temp->next;}//return the address of the head pointerreturn head;}void printLink(link* head){link* p=head;while(p){printf("%d ",p->elem);p=p->next;}printf("\n");}link* recursive_reverse(link* head) {// out recursive conditionif (head == NULL || head->next == NULL){return head;}else{//new_head always finds the address of the last element in the linked listlink *new_head = recursive_reverse(head->next);//After recursion, put the linked listhead->next->next = head;head->next = NULL;return new_head;}}int main(){link*p=initLink();printf("Original linked list: ");printLink(p);printf("Reverse linked list: ");p=recursive_reverse(p);printLink(p);return 0;}

Output result: