单链表反转

转载自http://blog.csdn.net/fx677588/article/details/72357389

链表的翻转是程序员面试中出现频度最高的问题之一，常见的解决方法分为递归和迭代两种。最近在复习的时候，发现网上的资料都只告诉了怎么做，但是根本没有好好介绍两种方法的实现过程与原理。所以我觉得有必要好好的整理一篇博文，来帮忙大家一步步理解其中的实现细节。 

我们知道迭代是从前往后依次处理，直到循环到链尾；而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。下面我会用详细的图文来剖析其中实现的细节。 

1、非递归（迭代）方式 

　　迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。

　　首先对于链表设置两个指针：

然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针NewH移向新的链表头，如下图所示。此处需要注意，不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。而是应该设置一个临时指针tmp，先暂时指向P->next指向的地址空间，保存原链表后续数据。然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。

　　指针继续向后移动，直到P指针指向NULL停止迭代。

　　最后一步：

2、非递归实现的程序 

Node*reverseList(node*H){

if(H==NULL||H->next==NULL)//链表为空或者仅1个数直接返回

returnH;   

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;

}

3、递归方式 

我们再来看看递归实现链表翻转的实现，前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表。 

　　首先指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。

然后H指针逐层返回的时候依次做下图的处理，将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。

　　继续返回操作：

　　上图第一次如果没有将存放4空间的next指针赋值指向NULL，第二次H->next->next=H，就会将存放5的地址空间覆盖为3，这样链表一切都大乱了。接着逐层返回下去，直到对存放1的地址空间处理。

　　返回到头：

4、迭代实现的程序 

Node *In_reverseList(node*H){

if(H==NULL||H->next==NULL)//链表为空直接返回，而H->next为空是递归基

returnH;

   Node *newHead=In_reverseList(H->next);//一直循环到链尾

H->next->next=H;//翻转链表的指向

H->next=NULL;//记得赋值NULL，防止链表错乱

return newHead;//新链表头永远指向的是原链表的链尾}

5、整体实现的程序： 

#includeusing 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个数直接返回returnH;    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指向的下一个空间}returnnewH;}/***递归方式***/node*In_reverseList(node*H){if(H==NULL||H->next==NULL)//链表为空直接返回，而H->next为空是递归基returnH;    node*newHead=In_reverseList(H->next);//一直循环到链尾 H->next->next=H;//翻转链表的指向H->next=NULL;//记得赋值NULL，防止链表错乱returnnewHead;//新链表头永远指向的是原链表的链尾}int main(){    node*first=newnode(1);    node*second=newnode(2);    node*third=newnode(3);    node*forth=newnode(4);    node*fifth=newnode(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);//再翻转return0;}