數據結構：反轉鏈表（reverse the linked list）

通過交換元素值實現反轉（reverse by swapping elements）

?滑動指針（sliding pointers）

使用滑動指針反轉鏈表（Reversing a Linked List using Sliding Pointers）

對比分析

如何用遞歸（Recursion）反轉一個單鏈表

通過交換元素值實現反轉（reverse by swapping elements）

為什么我們要講這個“交換值法”而不是先講“指針反轉”？

因為指針反轉屬于結構反轉，要修改鏈表的連接方式（更復雜）
而“交換值法”是數據反轉，結構不變，只是調換節點里的值，適合入門理解。

（可以參考類似問題：

數據結構：數組：反轉數組（Reverse the Array）-CSDN博客

數據結構：反轉字符串（Reversing a String）_string反轉字符串方法-CSDN博客）

第一性分析：什么是“反轉鏈表”？

假設你有如下鏈表：

head → [1] → [3] → [5] → [7] → NULL

反轉之后應該是：

head → [7] → [5] → [3] → [1] → NULL

你可以看到：鏈表結構（指針連接順序）完全不動，只是每個節點的 data 內容被調換了。

那么，第一性問題來了：

? 單鏈表只能順著走，你怎么訪問“最后一個節點”？

我們要反轉鏈表的“數據內容”，但不能直接隨機訪問鏈表，因為單鏈表只能一個方向逐個訪問。

所以，我們換一個角度：

用數組作為“中間容器”，把鏈表的數據轉移出來操作，然后再拷貝回鏈表。

為什么可以這樣做？

數組支持隨機訪問，反轉變得容易
鏈表結構不變，只是內容（data 字段）被替換
指針不涉及改動 → 安全、簡單

① 創建數組，邊遍歷鏈表邊復制 data

int arr[SIZE];  // 假設鏈表最多 SIZE 個節點
int count = 0;struct Node* temp = head;
while (temp != NULL) {arr[count++] = temp->data;temp = temp->next;
}

② 再次遍歷鏈表，這次寫入反轉值

temp = head;
for (int i = count - 1; i >= 0; i--) {temp->data = arr[i];temp = temp->next;
}

?? 注意：

你需要預估鏈表最多多少個節點（用 #define SIZE 100）
或者你可以動態分配數組

完整代碼實現

#include <stdio.h>
#include <stdlib.h>#define SIZE 100  // 預設最大節點數struct Node {int data;struct Node* next;
};void reverseDataWithArray(struct Node* head) {int arr[SIZE];int count = 0;struct Node* temp = head;// Step 1: 復制 data 到數組中while (temp != NULL) {arr[count++] = temp->data;temp = temp->next;}// Step 2: 再次遍歷鏈表，寫入反轉值temp = head;for (int i = count - 1; i >= 0; i--) {temp->data = arr[i];temp = temp->next;}
}void printList(struct Node* head) {while (head != NULL) {printf("%d → ", head->data);head = head->next;}printf("NULL\n");
}struct Node* createList() {struct Node* a = malloc(sizeof(struct Node));struct Node* b = malloc(sizeof(struct Node));struct Node* c = malloc(sizeof(struct Node));struct Node* d = malloc(sizeof(struct Node));a->data = 10; a->next = b;b->data = 20; b->next = c;c->data = 30; c->next = d;d->data = 40; d->next = NULL;return a;
}int main() {struct Node* head = createList();printf("Original list:\n");printList(head);reverseDataWithArray(head);printf("After reversing data (using array):\n");printList(head);return 0;
}

?滑動指針（sliding pointers）

第一性推導：從鏈表遍歷說起

單個指針遍歷鏈表：

你最開始遍歷鏈表時，通常會寫這樣的代碼：

struct Node* temp = head;
while (temp != NULL) {// 做點什么，比如打印 temp->datatemp = temp->next;
}

這沒問題，但注意：

當你執行 temp = temp->next; 之后，你就永遠失去了對原來 temp 的訪問

??問題出現：

如果你想在遍歷的過程中修改鏈表結構，比如：

刪除當前節點
插入新節點
調換兩個節點順序
反轉鏈表指向方向

你會發現只用一個 temp 指針是不夠的。在某些操作后失去訪問某個節點 → 鏈表斷開 → 崩潰?

舉個例子：嘗試改變指針方向

想象鏈表這樣：

head → [10] → [20] → [30] → NULL

?你拿著 curr = head，執行：

curr->next = NULL;

你現在就徹底失去了對 [20] 和 [30] 的訪問！因為鏈條被斷開，你再也找不到它們

🔍 第一性結論：

在進行結構操作（比如反轉、插入、刪除）時，你必須在操作之前保存“下一步”的信息

所以你就需要多個指針同時存在，它們滑動地一起遍歷鏈表，互相幫助保存位置

?這就是“滑動指針”的由來。

滑動指針是指你使用多個指針同時向前推進，每個指針記錄鏈表當前不同的“位置狀態”，它們就像滑動的窗口一樣，彼此協同完成操作。

舉例說明最基本的三個滑動指針：

假設我們有這些：

struct Node* prev = NULL;
struct Node* curr = head;
struct Node* next = NULL;

含義如下：

指針名稱	含義
`prev`	當前節點的前一個節點
`curr`	當前正在處理的節點
`next`	當前節點的下一個節點（提前保存）

它們在遍歷中這樣滑動：

每次迭代：

提前保存 curr->next 到 next
修改 curr->next = prev（如果你打算反轉）
整體滑動向前：

prev = curr;
curr = next;

?圖示（從左往右）：

prev → curr → next → ...

下一輪：

     prev → curr → next → ...

?什么時候需要滑動指針？

你需要三個滑動指針的操作包括但不限于：

?反轉鏈表
?刪除當前節點
?插入節點前后結構
?在不丟失鏈表結構的情況下做復雜重構

?? 為什么不只用一個或兩個指針？

你可以自己試一下用一個或兩個指針做“指針反轉”這種操作，你會發現：

總是有一個節點你無法訪問，就沒法完成鏈表重構，操作順序也錯了。

滑動指針讓你在每一步都有“前后備份”，所以操作安全可控。

?操作順序

next = curr->next;     // 提前保存下一步
curr->next = prev;     // 操作當前指針（反轉、插入、刪改）
prev = curr;           // 所有指針前滑
curr = next;

💡 第一性總結：

概念	解釋
為什么用多個指針	避免失去訪問鏈表節點的能力
指針的職責	prev：記錄已處理區域，curr：當前操作，next：保存未來節點
應用場景	修改鏈表結構時必須使用
本質思想	一邊操作鏈表，一邊維持三個位置的狀態，讓鏈不斷、訪問安全

使用滑動指針反轉鏈表（Reversing a Linked List using Sliding Pointers）

注意：不是改變節點里面的值，而是改變指針方向。

🚨 單鏈表只能從前往后遍歷

你不能往回走。所以：

每當你打算修改 curr->next，你必須提前保存 curr->next

所以，我們必須使用三個滑動指針：

struct Node* prev = NULL;
struct Node* curr = head;
struct Node* next = NULL;

名字	含義
`prev`	當前節點反轉后應該指向的“前一個”
`curr`	當前正在訪問的節點
`next`	提前保存的下一個節點

第一性步驟：每一次“滑動”都做這三步

next = curr->next;??→ 保存下一步
curr->next = prev;?→ 改變指向方向
prev = curr; curr = next;?→ 所有指針前移

空鏈表、一個節點怎么辦？

完全沒問題。curr == NULL 時循環直接跳過。

一個節點時，只走一輪，head 自動變成自己，反轉不出錯

步驟	目的
保存下一節點	防止修改 curr->next 后丟失后續鏈
修改 curr->next	實現反轉（原來向右，現在向左）
滑動三個指針	向前推進處理下一組節點
更新 head	將最終的 prev 作為新的鏈表頭

一步步構建反轉函數：reverseUsingPointers

void reverseUsingPointers(struct Node** head) {struct Node* prev = NULL;struct Node* curr = *head;struct Node* next = NULL;while (curr != NULL) {// Step 1: 提前保存下一步next = curr->next;// Step 2: 改變方向curr->next = prev;// Step 3: 所有指針滑動prev = curr;curr = next;}// 最終 prev 是新的頭部*head = prev;
}

對比分析

我們要比較兩種單鏈表反轉方式：

方法名稱	核心思路
方法一：拷貝數據法	將鏈表的 `data` 拷貝到數組，反轉后再寫回
方法二：滑動指針法（改變結構）	修改鏈表中每個節點的 `next` 指針方向

我們將從它們的本質、適用性、性能、安全性等方面一一分析。

1. 操作對象本質

?數據拷貝法：

只動數據，不動結構（next 不變）

arr[i] = temp->data;
temp->data = arr[j];

所以它適合在結構不能變動的情況下做反轉（如考試題、受限數據結構）

滑動指針法：

完全不動數據，只動結構（指針方向反過來）

curr->next = prev;

這本質上是“鏈表重構”，適合任何允許你改變鏈結構的環境，效率也更高

?2. 數據結構的復雜性影響

? 如果每個節點只存一個 int，拷貝沒什么壓力

但現實中常常這樣設計鏈表節點：

struct Node {char name[100];int id;float salary;struct Node* next;
};

這時候每個節點里的 data 是一個結構體（甚至可能更復雜）

→ 如果你用“拷貝數據法”，你必須完整復制這些字段

→ 可能需要自定義拷貝函數、深拷貝、數組容量等問題

當節點的 data 很復雜（結構體、嵌套對象、大量數據）時，滑動指針法明顯更好

3. 時間復雜度對比

操作	時間復雜度	原因
數據拷貝法	O(n) + O(n) = O(n)	兩次遍歷：拷貝 + 寫回
滑動指針法	O(n)	一次遍歷：邊滑動邊反轉指針

雖然復雜度都是 O(n)，但滑動指針法更省，只有一次遍歷和一次拷貝

4. 空間復雜度對比

方法	空間開銷	說明
拷貝數據法	O(n) 額外數組空間	存儲每個 `data` 的值
滑動指針法	O(1)（只用 3 個指針）	不需要額外數組

5. 安全性與一致性

?滑動指針法：

不會拷貝錯誤
不關心 data 內容是什么（結構再復雜都不管）
不會遇到內存越界等數組問題

?數據拷貝法：

要保證數組空間夠大
要小心拷貝結構體或深拷貝問題
容易寫錯或越界（尤其是動態鏈表）

因此，滑動指針法更通用、更安全、更節省空間，更適合實際工程和復雜數據結構，?數據拷貝法僅適合學習、數據簡單、結構不允許改動時使用?。

你應該選擇滑動指針法的理由總結：

不管節點里放什么，它都不在乎
永遠只用三個指針，不會爆內存
一次遍歷搞定，比拷貝更省時間
改變結構更符合“鏈表反轉”的語義

如何用遞歸（Recursion）反轉一個單鏈表

第一性原則出發點：什么是遞歸？

遞歸是指：一個函數在內部調用自己，并且有：

基本情況（Base Case）：終止條件
遞歸情況（Recursive Case）：把當前問題拆分成更小問題交給自己來做

第一步：遞歸函數的思考

?我們要問：我們可以用遞歸處理誰？

答案是：

讓遞歸先反轉鏈表的后面部分，我們只處理“當前節點和它的 next”

所以遞歸函數的含義可以設定為：

void Reverse(Node* prev, Node* curr)

curr：當前節點（當前要處理的）
prev：當前節點 curr?的前驅（上一個）

這是一個滑動指針式遞歸反轉方案。

你會從頭開始調用：

Reverse(NULL, head);

每一次遞歸，你都把當前 curr 當作下一輪的 prev，curr->next 當作下一輪的 curr

也就是說，每一層你都像這樣“向前推進”：

Reverse(curr, curr->next);

一層層推進（調用棧）：

調用層	prev	curr
1	NULL	1
2	1	2
3	2	3
4	3	4
5	4	NULL ← base case

第二步：Base Case（終止條件）

當你遞歸到最后一個節點，鏈表已經不能再往下了：

if (curr == NULL) {first = prev;return;
}

如果當前處理節點 curr?已經是 NULL，說明我們走到了原鏈表的末尾
此時 prev?是最后一個有效節點，應該變成新的頭節點
所以設置 first = prev（這個變量是全局的鏈表頭）

第三步：Recursive Case（遞歸處理）

每一層執行：

Reverse(curr, curr->next);

也就是說：

下一輪，curr?成為 prev
curr->next 成為新的 curr

這相當于向后滑動一格，保持一個“兩個指針的窗口”，像滑動指針一樣

第四步：反轉指針

遞歸完成之后，再回來時：

curr->next = prev;

你把當前節點的 next 指向前一個節點

🔄 反轉動作在哪里發生？

不是在前進時做的，而是在遞歸“回溯”過程中做的

用第一性逐層模擬

假設鏈表為：[1] → [2] → [3] → NULL

初始調用：

Reverse(NULL, 1)

→ 遞歸進入 Reverse(1, 2)
→ 遞歸進入 Reverse(2, 3)
→ 遞歸進入 Reverse(3, NULL)
→ 此時：curr?== NULL, 執行：first = prev?→ 即 first = 3?

然后回溯階段

curr = 3, prev = 2 → 3->next = 2  
curr = 2, prev = 1 → 2->next = 1  
curr = 1, prev = NULL → 1->next = NULL

得到新鏈表

first → [3] → [2] → [1] → NULL

階段	操作	含義
遞歸推進	`Reverse(curr, curr->next)`	保存前一個和當前節點，深入到末尾
遞歸終止	`if (curr == NULL)`	到達末尾，設置新的鏈表頭 `first = prev`
回溯反轉指向	`curr->next = prev`	每層反轉指向，把當前節點指向前一個節點

完整代碼

void Reverse(Node* prev, Node* curr) {if (curr != NULL) {Reverse(curr, curr->next);  // 向后推進curr->next = prev;          // 回溯過程中修改指向} else {first = prev;            // 遞歸到底，設置新頭}
}

為什么這種方法優雅？