[[281044]]

一. 序

鏈表作為一種基本的數(shù)據(jù)結(jié)構(gòu)，本身理解起來很簡單。它通過指針，將一組零散的內(nèi)存空間(結(jié)點)，串聯(lián)起來，組成一個數(shù)據(jù)結(jié)構(gòu)。

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

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

二. K 個一組翻轉(zhuǎn)鏈表

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

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

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

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

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

依據(jù)這幾個結(jié)點，就可以完成子鏈表的翻轉(zhuǎn)，以及保證在子鏈表翻轉(zhuǎn)后依然可以串起來。

另外有一個特殊處理的地方，當(dāng)原始鏈表以 K 個結(jié)點為一組分組時，末尾不滿一組的子鏈表，保持原樣不進行翻轉(zhuǎn)。

參考鏈表兩兩翻轉(zhuǎn)的思路，為了保證我們的代碼邏輯統(tǒng)一，我們增加一個虛擬的頭結(jié)點 dummy，來方便我們編寫代碼。

直接上代碼，細節(jié)都在注釋里。

class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 增加虛擬頭結(jié)點 ListNode dummy = new ListNode(0); dummy.next = head; // 定義 prev 和 end 結(jié)點 ListNode prev = dummy; ListNode end = dummy; while(end.next != null) { // 以 k 個結(jié)點為條件，分組子鏈表 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; // 翻轉(zhuǎn)子鏈表 prev.next = reverseList(start); // 將子連表前后串起來 start.next = next; prev = start; end = prev; } return dummy.next; } // 遞歸完成單鏈表翻轉(zhuǎn) 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; }}

這里單鏈表的翻轉(zhuǎn)，使用了遞歸，一般 K 值都不會太大，所以用遞歸沒問題，當(dāng)然你也可以換成循環(huán)實現(xiàn)。對細節(jié)不了解的，可以參見《單鏈表翻轉(zhuǎn)》。

三. 小結(jié)時刻

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

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

到這里，鏈表翻轉(zhuǎn)的基礎(chǔ)題，基本上就說清楚了，包含三個篇文章：

單鏈表翻轉(zhuǎn)。

鏈表雙雙翻轉(zhuǎn)。

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