链表的翻转是程序员面试中出现频度最高的问题之一，常见的解决方法分为递归和迭代两种。
1、非递归（迭代）方式
迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。
image.png
首先对于链表设置两个指针：
image.png
然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针NewH移向新的链表头，如下图所示。此处需要注意，不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。而是应该设置一个临时指针tmp，先暂时指向P->next指向的地址空间，保存原链表后续数据。然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。
image.png
指针继续向后移动，直到P指针指向NULL停止迭代。
image.png
最后一步：
image.png
非递归实现的代码
node* reverseList(node* H)
{
if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回
return H;
node* p = H, *newH = NULL;
while (p != NULL) //一直迭代到链尾
{
node* tmp = p->next; //暂存p下一个地址，防止变化指针指向后找不到后续的数
p->next = newH; //p->next指向前一个空间
newH = p; //新链表的头移动到p，扩长一步链表
p = tmp; //p指向原始链表p指向的下一个空间
}
return newH;
}
2、递归方式
我们再来看看递归实现链表翻转的实现，前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表。
首先指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。
image.png
然后H指针逐层返回的时候依次做下图的处理，将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。
image.png
继续返回操作：
image.png
上图第一次如果没有将存放4空间的next指针赋值指向NULL，第二次H->next->next=H，就会将存放5的地址空间覆盖为3，这样链表一切都大乱了。接着逐层返回下去，直到对存放1的地址空间处理。
image.png
返回到头：
image.png
迭代实现的代码
node* In_reverseList(node* H)
{
if (H == NULL || H->next == NULL) //链表为空直接返回，而H->next为空是递归基
return H;
node* newHead = In_reverseList(H->next); //一直循环到链尾
H->next->next = H; //翻转链表的指向
H->next = NULL; //记得赋值NULL，防止链表错乱
return newHead; //新链表头永远指向的是原链表的链尾
}
整体实现的程序：
#include<iostream>
using namespace std;
struct node{
int val;
struct node* next;
node(int x) :val(x){}
};
/***非递归方式***/
node* reverseList(node* H)
{
if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回
return H;
node* p = H, *newH = NULL;
while (p != NULL) //一直迭代到链尾
{
node* tmp = p->next; //暂存p下一个地址，防止变化指针指向后找不到后续的数
p->next = newH; //p->next指向前一个空间
newH = p; //新链表的头移动到p，扩长一步链表
p = tmp; //p指向原始链表p指向的下一个空间
}
return newH;
}
/***递归方式***/
node* In_reverseList(node* H)
{
if (H == NULL || H->next == NULL) //链表为空直接返回，而H->next为空是递归基
return H;
node* newHead = In_reverseList(H->next); //一直循环到链尾
H->next->next = H; //翻转链表的指向
H->next = NULL; //记得赋值NULL，防止链表错乱
return newHead; //新链表头永远指向的是原链表的链尾
}
int main()
{
node* first = new node(1);
node* second = new node(2);
node* third = new node(3);
node* forth = new node(4);
node* fifth = new node(5);
first->next = second;
second->next = third;
third->next = forth;
forth->next = fifth;
fifth->next = NULL;
//非递归实现
node* H1 = first;
H1 = reverseList(H1); //翻转
//递归实现
node* H2 = H1; //请在此设置断点查看H1变化，否则H2再翻转，H1已经发生变化
H2 = In_reverseList(H2); //再翻转
return 0;
}
网友评论