鏈表翻轉(zhuǎn)的圖文講解（遞歸與迭代兩種實(shí)現(xiàn)）
鏈表的翻轉(zhuǎn)是程序員面試中出現(xiàn)頻度最高的問題之一，常見的解決方法分為遞歸和迭代兩種。最近在復(fù)習(xí)的時(shí)候，發(fā)現(xiàn)網(wǎng)上的資料都只告訴了怎么做，但是根本沒有好好介紹兩種方法的實(shí)現(xiàn)過程與原理。所以我覺得有必要好好的整理一篇博文，來幫忙大家一步步理解其中的實(shí)現(xiàn)細(xì)節(jié)。?
我們知道迭代是從前往后依次處理，直到循環(huán)到鏈尾；而遞歸恰恰相反，首先一直迭代到鏈尾也就是遞歸基判斷的準(zhǔn)則，然后再逐層返回處理到開頭。總結(jié)來說，鏈表翻轉(zhuǎn)操作的順序?qū)τ诘鷣碚f是從鏈頭往鏈尾，而對(duì)于遞歸是從鏈尾往鏈頭。下面我會(huì)用詳細(xì)的圖文來剖析其中實(shí)現(xiàn)的細(xì)節(jié)。?
1、非遞歸（迭代）方式?
迭代的方式是從鏈頭開始處理，如下圖給定一個(gè)存放5個(gè)數(shù)的鏈表。
首先對(duì)于鏈表設(shè)置兩個(gè)指針：
然后依次將舊鏈表上每一項(xiàng)添加在新鏈表的后面，然后新鏈表的頭指針NewH移向新的鏈表頭，如下圖所示。此處需要注意，不可以上來立即將上圖中P->next直接指向NewH，這樣存放2的地址就會(huì)被丟棄，后續(xù)鏈表保存的數(shù)據(jù)也隨之無法訪問。而是應(yīng)該設(shè)置一個(gè)臨時(shí)指針tmp，先暫時(shí)指向P->next指向的地址空間，保存原鏈表后續(xù)數(shù)據(jù)。然后再讓P->next指向NewH，最后P=tmp就可以取回原鏈表的數(shù)據(jù)了，所有循環(huán)訪問也可以繼續(xù)展開下去。
指針繼續(xù)向后移動(dòng)，直到P指針指向NULL停止迭代。
最后一步：
2、非遞歸實(shí)現(xiàn)的程序?
node* reverseList(node* H)
{
? ? if (H == NULL || H->next == NULL) //鏈表為空或者僅1個(gè)數(shù)直接返回? ? ? ? return H;
? ? 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ò)長一步鏈表? ? ? ?
? ?p? ? = tmp;? ? ? ? ? ? ? ? ? //p指向原始鏈表p指向的下一個(gè)空間? ? }
? ? return newH;
}
3、遞歸方式?
我們?cè)賮砜纯催f歸實(shí)現(xiàn)鏈表翻轉(zhuǎn)的實(shí)現(xiàn)，前面非遞歸方式是從前面數(shù)1開始往后依次處理，而遞歸方式則恰恰相反，它先循環(huán)找到最后面指向的數(shù)5，然后從5開始處理依次翻轉(zhuǎn)整個(gè)鏈表。?
首先指針H迭代到底如下圖所示，并且設(shè)置一個(gè)新的指針作為翻轉(zhuǎn)后的鏈表的頭。由于整個(gè)鏈表翻轉(zhuǎn)之后的頭就是最后一個(gè)數(shù)，所以整個(gè)過程N(yùn)ewH指針一直指向存放5的地址空間。
然后H指針逐層返回的時(shí)候依次做下圖的處理，將H指向的地址賦值給H->next->next指針，并且一定要記得讓H->next =NULL，也就是斷開現(xiàn)在指針的鏈接，否則新的鏈表形成了環(huán)，下一層H->next->next賦值的時(shí)候會(huì)覆蓋后續(xù)的值。
繼續(xù)返回操作：
上圖第一次如果沒有將存放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為空是遞歸基
return H;
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ù)直接返回? ? ? ? return H;
? ? 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ò)長一步鏈表? ? ? ? p? ? = tmp;? ? ? ? ? ? ? ? ? //p指向原始鏈表p指向的下一個(gè)空間? ? }
? ? return newH;
}
/***遞歸方式***/
node* In_reverseList(node* H){
????if (H == NULL || H->next == NULL) //鏈表為空直接返回，而H->next為空是遞歸基
????return H;
????node* newHead = In_reverseList(H->next); //一直循環(huán)到鏈尾
????H->next->next = H; //翻轉(zhuǎn)鏈表的指向
????H->next = NULL; //記得賦值NULL，防止鏈表錯(cuò)亂
????return newHead; //新鏈表頭永遠(yuǎn)指向的是原鏈表的鏈尾
}
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; //非遞歸實(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)
return 0;
}
