LeetCode 25 - K 個一組翻轉鏈表

這道題是一個典型的鏈表操作題，考察我們對鏈表的精確操作，包括反轉鏈表、分組處理、遞歸和迭代的結合應用等。還可以通過變體問題延伸到優先隊列操作、歸并、分塊等，這使得它成為面試中的高頻考題之一。

---

題目描述

給你一個鏈表，每 k 個節點一組進行翻轉，并返回翻轉后的鏈表。

• k 是一個正整數，它的值小于或等于鏈表的長度。
• 如果節點總數不是 k 的整數倍，那么請將最后剩余節點保持原樣。
• 你不允許更改節點的值，只能調整節點指針的方向。

---

示例

輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]

---

解題思路與分析

核心簡化問題

1. 分段處理鏈表：將鏈表分成每 k 個一組。
2. 對每一組執行反轉操作。
3. 當遍歷到不足 k 個節點的部分時，維持原順序不再反轉。
4. 方法可以通過遞歸或迭代完成。

---

解法與代碼模板

解法 1：遞歸法

核心思路

• 使用遞歸配合局部反轉：
  1. 確定鏈表是否有足夠的 k 個節點：如果不足 k 個，直接返回頭節點。
  2. 如果有足夠的 k 個節點：
     • 完成當前組內 k 個節點的反轉，
     • 遞歸地對剩余部分鏈表繼續處理。
  3. 將當前反轉的部分連接到下一組遞歸結果。

模板代碼

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 檢查鏈表是否有足夠的 k 個節點ListNode current = head;int count = 0;while (current != null && count < k) {current = current.next;count++;}// 如果不足 k 個節點，直接返回原鏈表if (count < k) {return head;}// 反轉當前 k 個節點ListNode prev = null, next = null;current = head;for (int i = 0; i < k; i++) {next = current.next;   // 暫存下一節點current.next = prev;  // 改變指針方向prev = current;       // 移動 prev 指針current = next;       // 移動 current 指針}// 遞歸處理剩余鏈表，并連接反轉后的部分head.next = reverseKGroup(current, k);// 返回反轉后的頭節點return prev;}
}

復雜度分析

• 時間復雜度: O(N)
  • 每個節點僅訪問一次。
• 空間復雜度: O(N / k)
  • 遞歸調用棧的深度為 (鏈表長度 / k)。

優缺點

• 優點:代碼簡潔并且邏輯清晰，適合遞歸思路的場景。
• 缺點:會造成大量遞歸棧調用，鏈表很長時可能出現棧溢出。

---

解法 2：迭代法

核心思路

• 相對于遞歸法，用 迭代 來實現分組反轉鏈表，避免了遞歸棧空間的開銷：
  1. 使用 啞結點（dummy node）作為新鏈表的起始位置，方便連接。
  2. 遍歷鏈表，分別找到每一組的起始結點和結束結點。
  3. 將當前分組進行反轉，并連接到已經處理好的鏈表部分。
  4. 當剩余節點不足時，停止反轉，直接連接到尾部。

模板代碼

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 創建啞結點ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prevGroupEnd = dummy;while (true) {// 找到當前組的開始和結束節點ListNode groupStart = prevGroupEnd.next;ListNode groupEnd = prevGroupEnd;for (int i = 0; i < k; i++) {groupEnd = groupEnd.next;if (groupEnd == null) {return dummy.next; // 不足 k 個節點}}// 下一組的起始節點ListNode nextGroupStart = groupEnd.next;// 反轉當前組reverseList(groupStart, groupEnd);// 連接反轉后的部分prevGroupEnd.next = groupEnd; // 當前組的結尾變成起始點groupStart.next = nextGroupStart;// 更新 prevGroupEnd 為這一組的最后節點prevGroupEnd = groupStart;}}private void reverseList(ListNode start, ListNode end) {ListNode prev = null, current = start, next = null;ListNode stop = end.next; // 保存停止位置while (current != stop) {next = current.next;current.next = prev;prev = current;current = next;}}
}

復雜度分析

• 時間復雜度: O(N)
  • 每個節點最多被訪問兩次（反轉和連接）。
• 空間復雜度: O(1)
  • 沒有額外棧空間的使用，僅需常數級別指針。

優缺點

• 優點: 比遞歸方法更高效，適用于超長鏈表。
• 缺點: 實現邏輯上稍微復雜。

---

解法 3：棧輔助法

核心思路

• 借助棧來反轉每一組節點：
  1. 遍歷鏈表，將 k 個節點壓入棧中。
  2. 當棧中節點數量達到 k 時，出棧并重新連接節點指針。
  3. 如果節點數量不足 k，直接連接剩余部分。

模板代碼

import java.util.Stack;class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k <= 1) return head;Stack<ListNode> stack = new Stack<>();ListNode dummy = new ListNode(-1);ListNode prev = dummy;dummy.next = head;while (head != null) {// 將 k 個節點壓入棧for (int i = 0; i < k && head != null; i++) {stack.push(head);head = head.next;}// 判斷棧中是否有足夠的 k 個節點if (stack.size() == k) {// 出棧并重新連接while (!stack.isEmpty()) {prev.next = stack.pop();prev = prev.next;}prev.next = head; // 連接當前組與下一組}}return dummy.next;}
}

復雜度分析

• 時間復雜度: O(N)
  • 每個節點入棧、出棧一次。
• 空間復雜度: O(k)
  • 棧空間用于存儲每組 k 個節點。

優點和缺點

• 優點: 實現簡單，不需要復雜鏈表反轉邏輯。
• 缺點: 額外使用棧空間，適用于較短鏈表。

---

經典變體問題

變體 1：反轉鏈表 II

• 反轉鏈表的第 m 到第 n 個節點（LeetCode 92）。
• 解法類似，利用迭代進行指定區域反轉。

---

變體 2：K 個一組翻轉鏈表，但跳過一些組

• 例如：對鏈表分組，但只翻轉奇數組或者僅反轉偶數組。

---

變體 3：分組排序

• 例如：對鏈表的每組節點排序而不是反轉。

---

快速 AC 總結

1. 遞歸與迭代優先掌握：
   • 遞歸：邏輯清晰但容易出現棧溢出，適用于理論驗證。
   • 迭代：高效且空間復雜度較低，是面試中優選方法。
2. 啞節點技巧：
   • 在處理鏈表操作時，借助啞節點可以避免很多冗余的頭節點邊界條件處理。
3. 多練變體問題：
   • 如部分反轉、跳過反轉的場景，可以輕松遷移基礎模板。

通過對鏈表反轉操作的熟悉，配合經典模板化實現，可以快速應對鏈表轉化類問題，并高效解決工程中復雜數據結構操作場景。