轉(zhuǎn)載自http://blog.csdn.net/fx677588/article/details/72357389
鏈表的翻轉(zhuǎn)是程序員面試中出現(xiàn)頻度最高的問(wèn)題之一洗鸵，常見(jiàn)的解決方法分為遞歸和迭代兩種悴侵。最近在復(fù)習(xí)的時(shí)候喧伞，發(fā)現(xiàn)網(wǎng)上的資料都只告訴了怎么做，但是根本沒(méi)有好好介紹兩種方法的實(shí)現(xiàn)過(guò)程與原理。所以我覺(jué)得有必要好好的整理一篇博文，來(lái)幫忙大家一步步理解其中的實(shí)現(xiàn)細(xì)節(jié)折砸。?
我們知道迭代是從前往后依次處理，直到循環(huán)到鏈尾沙峻；而遞歸恰恰相反睦授，首先一直迭代到鏈尾也就是遞歸基判斷的準(zhǔn)則，然后再逐層返回處理到開(kāi)頭摔寨∪ゼ希總結(jié)來(lái)說(shuō)，鏈表翻轉(zhuǎn)操作的順序?qū)τ诘鷣?lái)說(shuō)是從鏈頭往鏈尾，而對(duì)于遞歸是從鏈尾往鏈頭删顶。下面我會(huì)用詳細(xì)的圖文來(lái)剖析其中實(shí)現(xiàn)的細(xì)節(jié)竖螃。?
1、非遞歸（迭代）方式?
迭代的方式是從鏈頭開(kāi)始處理逗余，如下圖給定一個(gè)存放5個(gè)數(shù)的鏈表特咆。
首先對(duì)于鏈表設(shè)置兩個(gè)指針：
然后依次將舊鏈表上每一項(xiàng)添加在新鏈表的后面，然后新鏈表的頭指針NewH移向新的鏈表頭录粱，如下圖所示腻格。此處需要注意，不可以上來(lái)立即將上圖中P->next直接指向NewH啥繁，這樣存放2的地址就會(huì)被丟棄菜职，后續(xù)鏈表保存的數(shù)據(jù)也隨之無(wú)法訪(fǎng)問(wèn)。而是應(yīng)該設(shè)置一個(gè)臨時(shí)指針tmp输虱，先暫時(shí)指向P->next指向的地址空間些楣，保存原鏈表后續(xù)數(shù)據(jù)脂凶。然后再讓P->next指向NewH宪睹，最后P=tmp就可以取回原鏈表的數(shù)據(jù)了，所有循環(huán)訪(fǎng)問(wèn)也可以繼續(xù)展開(kāi)下去蚕钦。
指針繼續(xù)向后移動(dòng)亭病，直到P指針指向NULL停止迭代。
最后一步：
2嘶居、非遞歸實(shí)現(xiàn)的程序?
Node*reverseList(node*H){
if(H==NULL||H->next==NULL)//鏈表為空或者僅1個(gè)數(shù)直接返回
returnH;? ?
Node? * p=H, *newH=NULL;
while(p!=NULL)//一直迭代到鏈尾
{? ? ? ?
Node *tmp=p->next;//暫存p下一個(gè)地址罪帖，防止變化指針指向后找不到后續(xù)的數(shù) ? ? ?? p->next=newH;//p->next指向前一個(gè)空間
newH=p;//新鏈表的頭移動(dòng)到p，擴(kuò)長(zhǎng)一步鏈表
p=tmp;//p指向原始鏈表p指向的下一個(gè)空間
}
return? newH;
}
3邮屁、遞歸方式?
我們?cè)賮?lái)看看遞歸實(shí)現(xiàn)鏈表翻轉(zhuǎn)的實(shí)現(xiàn)整袁，前面非遞歸方式是從前面數(shù)1開(kāi)始往后依次處理，而遞歸方式則恰恰相反佑吝，它先循環(huán)找到最后面指向的數(shù)5坐昙，然后從5開(kāi)始處理依次翻轉(zhuǎn)整個(gè)鏈表。?
首先指針H迭代到底如下圖所示芋忿，并且設(shè)置一個(gè)新的指針作為翻轉(zhuǎn)后的鏈表的頭炸客。由于整個(gè)鏈表翻轉(zhuǎn)之后的頭就是最后一個(gè)數(shù)，所以整個(gè)過(guò)程N(yùn)ewH指針一直指向存放5的地址空間戈钢。
然后H指針逐層返回的時(shí)候依次做下圖的處理痹仙，將H指向的地址賦值給H->next->next指針，并且一定要記得讓H->next =NULL殉了，也就是斷開(kāi)現(xiàn)在指針的鏈接开仰，否則新的鏈表形成了環(huán)，下一層H->next->next賦值的時(shí)候會(huì)覆蓋后續(xù)的值。
繼續(xù)返回操作：
上圖第一次如果沒(méi)有將存放4空間的next指針賦值指向NULL抖所，第二次H->next->next=H梨州，就會(huì)將存放5的地址空間覆蓋為3，這樣鏈表一切都大亂了田轧。接著逐層返回下去暴匠，直到對(duì)存放1的地址空間處理。
返回到頭：
4傻粘、迭代實(shí)現(xiàn)的程序?
Node *In_reverseList(node*H){
if(H==NULL||H->next==NULL)//鏈表為空直接返回每窖，而H->next為空是遞歸基
returnH;
?? Node *newHead=In_reverseList(H->next);//一直循環(huán)到鏈尾
H->next->next=H;//翻轉(zhuǎn)鏈表的指向
H->next=NULL;//記得賦值NULL，防止鏈表錯(cuò)亂
return newHead;//新鏈表頭永遠(yuǎn)指向的是原鏈表的鏈尾}
5弦悉、整體實(shí)現(xiàn)的程序：?
#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個(gè)數(shù)直接返回returnH;? ? node*p=H,*newH=NULL;while(p!=NULL)//一直迭代到鏈尾{? ? ? ? node*tmp=p->next;//暫存p下一個(gè)地址窒典，防止變化指針指向后找不到后續(xù)的數(shù)p->next=newH;//p->next指向前一個(gè)空間newH=p;//新鏈表的頭移動(dòng)到p，擴(kuò)長(zhǎng)一步鏈表p=tmp;//p指向原始鏈表p指向的下一個(gè)空間}returnnewH;}/***遞歸方式***/node*In_reverseList(node*H){if(H==NULL||H->next==NULL)//鏈表為空直接返回稽莉，而H->next為空是遞歸基returnH;? ? node*newHead=In_reverseList(H->next);//一直循環(huán)到鏈尾 H->next->next=H;//翻轉(zhuǎn)鏈表的指向H->next=NULL;//記得賦值NULL瀑志，防止鏈表錯(cuò)亂returnnewHead;//新鏈表頭永遠(yuǎn)指向的是原鏈表的鏈尾}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;//非遞歸實(shí)現(xiàn)node*H1=first;? ? H1=reverseList(H1);//翻轉(zhuǎn)//遞歸實(shí)現(xiàn)node*H2=H1;//請(qǐng)?jiān)诖嗽O(shè)置斷點(diǎn)查看H1變化，否則H2再翻轉(zhuǎn)污秆，H1已經(jīng)發(fā)生變化H2=In_reverseList(H2);//再翻轉(zhuǎn)return0;}
