連結清單的翻轉是程式員面試中出現頻度最高的問題之一，常見的解決方法分為遞歸和疊代兩種。最近在複習的時候，發現網上的資料都隻告訴了怎麼做，但是根本沒有好好介紹兩種方法的實作過程與原理。是以我覺得有必要好好的整理一篇博文，來幫忙大家一步步了解其中的實作細節。
我們知道疊代是從前往後依次處理，直到循環到鍊尾；而遞歸恰恰相反，首先一直疊代到鍊尾也就是遞歸基判斷的準則，然後再逐層傳回處理到開頭。總結來說，連結清單翻轉操作的順序對于疊代來說是從鍊頭往鍊尾，而對于遞歸是從鍊尾往鍊頭。下面我會用詳細的圖文來剖析其中實作的細節。
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個數直接傳回
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
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為空是遞歸基
return H;
node* newHead = In_reverseList(H->next); //一直循環到鍊尾
H->next->next = H; //翻轉連結清單的指向
H->next = NULL; //記得指派NULL，防止連結清單錯亂
return newHead; //新連結清單頭永遠指向的是原連結清單的鍊尾
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
5、整體實作的程式：
#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();
node* second = new node();
node* third = new node();
node* forth = new node();
node* fifth = new node();
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 ;
}