递归反转链表
本篇包含反转打印和真实反转，坐稳发车！
一、递归打印链表
我们要实现的效果是先正向打印链表，随后再反转打印链表，本质上链表并未有任何变化
比如这个链表，我们要实现打印2 6 5 4，接着是4 5 6 2
首先实现正向打印
#include<stdio.h>#include<stdlib.h>struct Node{ int data; struct Node *next;};void Print(struct Node *p){ if(p==NULL)return;//防止无限递归 printf("%d",p->data);//先打印当前数据 Print(p->next);//递归继续调用函数}struct Node* Insert(struct Node *head,int data){ struct Node *temp=(struct Node*)malloc(sizeof(struct Node)); temp->data=data; temp->next=NULL; if(head==NULL){ head=temp; return head; } struct Node *temp2=head; while(temp2->next!=NULL){ temp2=temp2->next; } temp2->next=temp; return head;};
int main(){ struct Node *head=NULL; head=Insert(head,2); head=Insert(head,4); head=Insert(head,6); head=Insert(head,5); Print(head);}那么如何反转打印链表呢？？？🤔
仅仅需要先递归后打印即可！
void RPrint(struct Node *p){ if(p==NULL)return;//防止无限递归 Print(p->next);//递归继续调用函数 printf("%d",p->data);//先打印当前数据}完整c代码
#include<stdio.h>#include<stdlib.h>struct Node{ int data; struct Node *next;};void Print(struct Node *p){ if(p==NULL)return;//防止无限递归 printf("%d",p->data);//先打印当前数据 Print(p->next);//递归继续调用函数}void RPrint(struct Node *p){ if(p==NULL)return;//防止无限递归 Print(p->next);//递归继续调用函数 printf("%d",p->data);//后打印当前数据}struct Node* Insert(struct Node *head,int data){ struct Node *temp=(struct Node*)malloc(sizeof(struct Node)); temp->data=data; temp->next=NULL; if(head==NULL){ head=temp; return head; } struct Node *temp2=head; while(temp2->next!=NULL){ temp2=temp2->next; } temp2->next=temp; return head;};
int main(){ struct Node *head=NULL; head=Insert(head,2); head=Insert(head,4); head=Insert(head,6); head=Insert(head,5); Print(head); printf("\n"); RPrint(head);}
函数调用栈从main()开始！（忽略哪些Insert）接着进入Print(100)中，首先会执行printf("%d",p->data);打印当前数据，接着执行Print(p->next);进入Print(200)中，后面也是一样啦！😎
我们来从内存的视角看一看，栈里面有局部变量和函数，而堆里面有new或者malloc的东东😋
下图是Print函数调用过程
main先入栈，后续Print跟着入栈，而栈遵循先进后出的原则，所以出栈顺序看图是从上往下。
而在RPrint函数中，我们先递归再打印。
我们将上图左边所有Print看成RPrint，由于栈是遵循先进后出的原则，又因为是先递归再打印，所以会从最后一个执行的RPrint函数开始退出，并且退出后会打印数据然后下一个栈开始退出，这就造成了反转打印的效果。
Print(p->next);//递归继续调用函数printf("%d",p->data);//后打印当前数据递归相比迭代会消耗大量内存，从上图就可以看出来！🤔但是有时候，递归还是有很大的用处的！
二、递归实现反转链表
假设我们要反转的链表如下
结果如下
接着上面反转打印的栗子，我们来简单实现一下
struct Node* Reverse(struct Node *current){ if(current==NULL||current->next==NULL){//处理单链表或者空链表,也用于遍历到末尾，返回新head return current; } Reverse(head->next);}这样只能修改我们的head指针，因此我们还需要在出栈时（出栈相当于原路返回遍历链表！）进行操作
因此我们继续修改代码
struct Node* Reverse(struct Node *current){ if(current==NULL||current->next==NULL){//这是退出递归的条件，功能是遍历链表到达尾部 return current; } struct Node* newhead = Reverse(current->next); // 反转当前连接 struct Node *q = current->next; q->next=current; // 让下一个节点指向当前节点 current->next = NULL; // 断开当前节点的原连接 return newhead;}//7,8两行可以优化成 current->next->next=current;来看看出栈时的样子
接着几个Reverse函数出栈也是一样的操作，大佬们可以画图理解一下🤔
current->next=NULL这个设计很巧妙！它断开了原有的150指向250的连接，也为最左边节点指向NULL做了铺垫！😎
三、疑惑？
struct Node* Reverse(struct Node *current){ if(current==NULL||current->next==NULL){//这是退出递归的条件，功能是遍历链表到达尾部 return current; } struct Node* newhead = Reverse(current->next); // 反转当前连接 struct Node *q = current->next; q->next=current; // 让下一个节点指向当前节点 current->next = NULL; // 断开当前节点的原连接 return newhead;}你可能会好奇，Reverse有这么多返回值，到底会返回什么呢？？？又是current又是newhead的？好绕啊！
实际上，我们从调用栈的角度理解一下。
只有走到Reverse（250）会进入if条件，然后return！return 了 newhead，来自->newhead = Reverse(current->next);
而后续进行出栈的过程也就是下面
struct Node* newhead = Reverse(current->next); // 反转当前连接 struct Node *q = current->next; q->next=current; // 让下一个节点指向当前节点 current->next = NULL; // 断开当前节点的原连接 return newhead;newhead一直都是Reverse（250）返回的current，也就是说整个递归过程返回的值都是最终的current（也就是被main里面赋值为head的那个指针！）
大体过程抽象为如下。
Reverse(C) → returns C ↑Reverse(B) → receives C, returns C ↑Reverse(A) → receives C, returns C ↑main() → gets C as newHead有点烧脑。
部分信息可能已经过时