單向鏈表反轉的實現方法

?

https://www.zhihu.com/question/441865393/answer/3208578798

?

單向鏈表反轉是數據結構中的經典問題，在面試和實際開發中經常遇到。以下是 多種實現方式（包括遞歸和迭代），以 Go 語言為例。

---

1. 單向鏈表結構定義

type ListNode struct {Val  intNext *ListNode
}

---

2. 迭代法（推薦）

思路：

• 使用 三個指針 prev、curr、next，逐個反轉節點指向。
• 時間復雜度 O(n)，空間復雜度 O(1)（僅用常量額外空間）。

代碼實現

func reverseList(head *ListNode) *ListNode {var prev *ListNode  // 前驅節點curr := head        // 當前節點for curr != nil {next := curr.Next  // 暫存下一個節點curr.Next = prev   // 反轉指向prev = curr        // prev 后移curr = next        // curr 后移}return prev  // 返回新頭節點
}

示例：

輸入: 1 -> 2 -> 3 -> nil  
輸出: 3 -> 2 -> 1 -> nil

---

3. 遞歸法

思路：

• 遞歸到鏈表末尾，然后逐層反轉指針。
• 時間復雜度 O(n)，空間復雜度 O(n)（遞歸棧開銷）。

代碼實現

func reverseList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head  // 遞歸終止條件}newHead := reverseList(head.Next)  // 遞歸到末尾head.Next.Next = head              // 反轉指針head.Next = nil                    // 避免循環引用return newHead
}

執行過程：

reverseList(1):reverseList(2):reverseList(3): return 32.Next.Next = 2 → 3 -> 22.Next = nil → 3 -> 2 -> nil
1.Next.Next = 1 → 2 -> 1
1.Next = nil → 3 -> 2 -> 1 -> nil

---

4. 頭插法（利用啞節點）

思路：

• 遍歷鏈表，將每個節點插入到 啞節點（Dummy Node） 之后。
• 時間復雜度 O(n)，空間復雜度 O(1)。

代碼實現

func reverseList(head *ListNode) *ListNode {dummy := &ListNode{}  // 啞節點for head != nil {next := head.Next      // 暫存下一個節點head.Next = dummy.Next // 頭插dummy.Next = head      // 更新啞節點指向head = next            // 移動 head}return dummy.Next
}

流程示例：

初始: dummy -> nil, 鏈表: 1 -> 2 -> 3 -> nil第1步: dummy -> 1 -> nil  
第2步: dummy -> 2 -> 1 -> nil  
第3步: dummy -> 3 -> 2 -> 1 -> nil

---

5. 對比總結

方法	時間復雜度	空間復雜度	適用場景
迭代法	O(n)	O(1)	大多數情況（推薦）
遞歸法	O(n)	O(n)	代碼簡潔，但棧溢出風險
頭插法	O(n)	O(1)	需要啞節點輔助

---

6. 測試用例

func printList(head *ListNode) {for head != nil {fmt.Print(head.Val, " -> ")head = head.Next}fmt.Println("nil")
}func main() {head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}printList(head)          // 1 -> 2 -> 3 -> nilnewHead := reverseList(head)printList(newHead)       // 3 -> 2 -> 1 -> nil
}

---

7. 常見問題

Q1：遞歸法的缺點？

• 鏈表過長時可能導致 棧溢出（Stack Overflow）。
• 遞歸調用有額外空間開銷。

Q2：如何優化遞歸法？

• 某些編譯器支持 尾遞歸優化（Tail Call Optimization, TCO），但 Go 目前不支持。

Q3：迭代法為什么更推薦？

• 無棧溢出風險，適合處理超長鏈表。
• 空間效率更高（O(1)）。

---

掌握單向鏈表反轉是理解指針操作的基礎，建議手寫實現并測試邊界條件（如空鏈表、單節點鏈表）。