[[281044]]

一. 序

鏈表作為一種基本的數據結構，本身理解起來很簡單。它通過指針，將一組零散的內存空間(結點)，串聯起來，組成一個數據結構。

在面試的算法題中，經常會碰到鏈表相關的面試題。雖然鏈表的結構比較好理解，但是鏈表的題還是比較考驗代碼能力的。一些單鏈表的題，指針指來指去，很容易就把結點的 next 指針弄丟了，造成鏈表斷裂。

鏈表翻轉是一個面試中經常會碰到的題，在之前的文章中，也聊過單鏈表翻轉、鏈表雙雙翻轉(點擊藍字可跳轉了解)，今天再來聊聊它們的「升級版」，以 K 個為一組，翻轉鏈表，同時這也是 LeetCode 的第 25 題。

二. K 個一組翻轉鏈表

以 K 個結點為一組，將給定的單鏈表進行翻轉。有點類似之前的鏈表兩兩翻轉，只是那時的 K = 2。而在這道題中，K 變成一個外部傳入的正整數，它是一個可變的值，并且小于或者等于鏈表的長度。

這道算法題，會用到之前的知識，既然 K 是可變的，我們無法估計 K 的大小，但是我們可以將原始鏈表，以 K 個結點為一組，執行單鏈表翻轉的邏輯。

這就要用到之前《單鏈表翻轉》的技巧了，不了解的建議先讀讀之前的文章。

既然需要將原始鏈表先以 K 個結點分組，再依次執行單鏈表翻轉，在每組字鏈表翻轉之后，還需要將它們再串起來，否則鏈表不就斷裂了么。

這就需要使用兩個變量 prev 和 end，分別記錄子鏈表的前驅結點，以及子鏈表的尾結點。有了 end 這個子鏈表的尾結點，就可以很容易通過 end.next 拿到下一個子鏈表的頭結點。

依據這幾個結點，就可以完成子鏈表的翻轉，以及保證在子鏈表翻轉后依然可以串起來。

另外有一個特殊處理的地方，當原始鏈表以 K 個結點為一組分組時，末尾不滿一組的子鏈表，保持原樣不進行翻轉。

參考鏈表兩兩翻轉的思路，為了保證我們的代碼邏輯統一，我們增加一個虛擬的頭結點 dummy，來方便我們編寫代碼。

直接上代碼，細節都在注釋里。

class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 增加虛擬頭結點 ListNode dummy = new ListNode(0); dummy.next = head; // 定義 prev 和 end 結點 ListNode prev = dummy; ListNode end = dummy; while(end.next != null) { // 以 k 個結點為條件，分組子鏈表 for (int i = 0; i < k && end != null; i++) end = end.next; // 不足 K 個時不處理 if (end == null) break; // 處理子鏈表 ListNode start = prev.next; ListNode next = end.next; end.next = null; // 翻轉子鏈表 prev.next = reverseList(start); // 將子連表前后串起來 start.next = next; prev = start; end = prev; } return dummy.next; } // 遞歸完成單鏈表翻轉 private ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; }}

這里單鏈表的翻轉，使用了遞歸，一般 K 值都不會太大，所以用遞歸沒問題，當然你也可以換成循環實現。對細節不了解的，可以參見《單鏈表翻轉》。

三. 小結時刻

到這里單鏈表，按 K 分組翻轉的具體思路和代碼，就介紹清楚了。我這種處理方式可能不是最高效的，但是應該是比較清晰的。

另外在實際面試中，其實很多場景下，都不會直接出 leetcode 上的算法題，都會稍微變種一下，但是大家要學會將復雜問題，轉化為簡單問題來解決。

到這里，鏈表翻轉的基礎題，基本上就說清楚了，包含三個篇文章：

單鏈表翻轉。

鏈表雙雙翻轉。

鏈表以 K 個一組翻轉(本文)。