鏈表反轉(zhuǎn)的原理和方法
鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列的節(jié)點組成，每個節(jié)點包含一個數(shù)據(jù)域和一個指針域。鏈表的特點是可以靈活地增加或刪除節(jié)點，而不需要連續(xù)的內(nèi)存空間。鏈表有單向鏈表、雙向鏈表、循環(huán)鏈表等不同類型。
鏈表反轉(zhuǎn)是指將一個鏈表中的節(jié)點順序顛倒過來，使得原來的頭節(jié)點變成尾節(jié)點，原來的尾節(jié)點變成頭節(jié)點，以及原來的每個節(jié)點都指向它的前一個節(jié)點。例如，如圖 1 所示：
經(jīng)過反轉(zhuǎn)后，得到的新鏈表如圖 2 所示：
通過對比圖 1 和 圖 2 中的鏈表不難得知，所謂反轉(zhuǎn)鏈表，就是將鏈表整體“反過來”，將頭變成尾、尾變成頭。
那么如何實現(xiàn)這樣一個操作呢？常用的實現(xiàn)方案有以下幾種：
- 迭代反轉(zhuǎn)法
- 遞歸反轉(zhuǎn)法
- 就地逆置法
- 頭插法
下面我們分別介紹這些方法，并給出相應(yīng)的示例代碼和注釋。
1. 迭代反轉(zhuǎn)法
該算法的實現(xiàn)思想非常直接，就是從當(dāng)前鏈表的首元節(jié)點開始，一直遍歷至鏈表的最后一個節(jié)點，這期間會逐個改變所遍歷到的節(jié)點的指針域，另其指向前一個節(jié)點。
具體地說，我們需要借助三個指針來完成這個操作：
-
prev：指向當(dāng)前遍歷到的節(jié)點之前（左邊）已經(jīng)被反轉(zhuǎn)過了部分子列表中最后（右邊）一個元素。 -
cur：指向當(dāng)前遍歷到并且正在被處理（即要被翻轉(zhuǎn)）部分子列表中第一個（左邊）元素。 -
next：用于保存當(dāng)前遍歷到并且正在被處理部分子列表中第二個（右邊）元素。
初始時，prev 指向空（因為還沒有任何元素被翻轉(zhuǎn)），cur 指向首元結(jié)點（因為首元結(jié)點是第一個要被翻轉(zhuǎn)），next 指向第二個結(jié)點（因為要保存下一個要被翻轉(zhuǎn)）。如圖 3 所示：
然后我們開始迭代地執(zhí)行以下步驟1：
- 將
cur->next指針改為指向prev - 將
prev指針移動到cur - 將
cur指針移動到next - 將
next指針到cur->next
重復(fù)這些步驟，直到 cur 指向空（即鏈表的最后一個節(jié)點的后一個位置），此時 prev 指向鏈表的最后一個節(jié)點（即反轉(zhuǎn)后的首元節(jié)點），如圖 4 所示：
因此，我們只需要返回 prev 即可得到反轉(zhuǎn)后的鏈表。
用 C 語言實現(xiàn)該算法的示例代碼如下1：
// 定義鏈表結(jié)點結(jié)構(gòu)體
struct ListNode {
int val; // 數(shù)據(jù)域
struct ListNode *next; // 指針域
};
// 迭代反轉(zhuǎn)法
struct ListNode* reverseList(struct ListNode* head) {
// 定義三個指針 prev、cur、next
struct ListNode *prev = NULL;
struct ListNode *cur = head;
struct ListNode *next = NULL;
// 遍歷鏈表，逐個改變指針域的指向
while (cur != NULL) {
next = cur->next; // 保存下一個要被處理的節(jié)點
cur->next = prev; // 將當(dāng)前節(jié)點指向前一個節(jié)點
prev = cur; // 將前一個節(jié)點移動到當(dāng)前節(jié)點
cur = next; // 將當(dāng)前節(jié)點移動到下一個要被處理的節(jié)點
}
return prev; // 返回反轉(zhuǎn)后的鏈表頭結(jié)點
}
2. 遞歸反轉(zhuǎn)法
該算法和迭代反轉(zhuǎn)法的思想恰好相反，它是從鏈表的尾節(jié)點開始，依次向前遍歷，遍歷過程中依次改變各節(jié)點的指針域，使其指向前一個節(jié)點。
具體地說，我們需要借助兩個指針來完成這個操作：
-
head：指向當(dāng)前正在被處理（即要被翻轉(zhuǎn)）部分子列表中第一個（左邊）元素。 -
new_head：用于保存已經(jīng)被處理過了部分子列表中第一個（左邊）元素。
初始時，head 指向首元結(jié)點（因為首元結(jié)點是第一個要被翻轉(zhuǎn)），new_head 指向空（因為還沒有任何元素被翻轉(zhuǎn)）。如圖 5 所示：
然后我們開始遞歸地執(zhí)行以下步驟：
- 如果
head或者head->next是空，則返回head - 否則，將
head->next節(jié)點作為新的head繼續(xù)遞歸調(diào)用本函數(shù)，并將結(jié)果賦值給new_head - 將原來的
head->next->next指針改為指向原來的head - 將原來的
head->next指針改為指向空
重復(fù)這些步驟，直到遞歸結(jié)束，此時返回值就是反轉(zhuǎn)后的鏈表頭結(jié)點。如圖 6 所示：
用 C 語言實現(xiàn)該算法的示例代碼如下
// 定義鏈表結(jié)點結(jié)構(gòu)體
struct ListNode {
int val; // 數(shù)據(jù)域
struct ListNode *next; // 指針域
};
// 遞歸反轉(zhuǎn)法
struct ListNode* reverseList(struct ListNode* head) {
// 定義兩個指針 head 和 new_head
struct ListNode *new_head = NULL;
// 如果 head 或者 head->next 是空，則返回 head
if (head == NULL || head->next == NULL) {
return head;
}
// 否則，將 head->next 節(jié)點作為新的 head 繼續(xù)遞歸調(diào)用本函數(shù)，并將結(jié)果賦值給 new_head
new_head = reverseList(head->next);
// 將原來的 head->next->next 指針改為指向原來的 head
head->next->next = head;
// 將原來的 head->next 指針改為指向空
head->next = NULL;
return new_head; // 返回反轉(zhuǎn)后的鏈表頭結(jié)點
}
3. 頭插法
該算法是利用一個新建的空鏈表（帶頭節(jié)點或不帶頭節(jié)點均可），遍歷原鏈表，將每個遍歷到的節(jié)點插入到新鏈表的首部，從而實現(xiàn)鏈表反轉(zhuǎn)。
具體地說，我們需要借助三個指針來完成這個操作：
-
head：指向原鏈表中當(dāng)前正在被處理（即要被翻轉(zhuǎn)）部分子列表中第一個（左邊）元素。 -
cur：指向原鏈表中當(dāng)前正在被處理（即要被翻轉(zhuǎn)）部分子列表中最后一個（右邊）元素。 -
new_head：指向新建空鏈表中第一個（左邊）元素。
初始時，head 指向首元結(jié)點（因為首元結(jié)點是第一個要被翻轉(zhuǎn)），cur 指向空（因為還沒有任何元素被翻轉(zhuǎn)），new_head 指向新建空鏈表中唯一的頭節(jié)點。如圖 7 所示：
然后我們開始迭代地執(zhí)行以下步驟
- 如果
head是空，則返回new_head - 否則，將
head節(jié)點從原鏈表中斷開，并保存其下一個節(jié)點到cur - 將
head節(jié)點插入到新鏈表的首部，即將其放在new_head的后面，并更新new_head - 將
cur節(jié)點作為新的head
重復(fù)這些步驟，直到迭代結(jié)束，此時返回值就是反轉(zhuǎn)后的鏈表頭結(jié)點。如圖 8 所示：
用 C 語言實現(xiàn)該算法的示例代碼如下
// 頭插法
struct ListNode* reverseList(struct ListNode* head) {
// 定義一個新建的空鏈表 new_head
struct ListNode *new_head = NULL;
// 定義一個指針 cur 用來保存 head 的下一個節(jié)點
struct ListNode *cur = NULL;
// 迭代地執(zhí)行以下步驟
while (head != NULL) {
// 將 head 節(jié)點從原鏈表中斷開，并保存其下一個節(jié)點到 cur
cur = head->next;
// 將 head 節(jié)點插入到新鏈表的首部，即將其放在 new_head 的后面，并更新 new_head
head->next = new_head;
new_head = head;
// 將 cur 節(jié)點作為新的 head
head = cur;
}
return new_head; // 返回反轉(zhuǎn)后的鏈表頭結(jié)點
}
這樣就完成了頭插法反轉(zhuǎn)鏈表
