[[281044]]

一. 序

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

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

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

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

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

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

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

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

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

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

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

參考鏈表兩兩翻轉(zhuǎn)的思路，為了保證我們的代碼邏輯統(tǒng)一，我們?cè)黾右粋€(gè)虛擬的頭結(jié)點(diǎn) dummy，來方便我們編寫代碼。

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

class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 增加虛擬頭結(jié)點(diǎn) ListNode dummy = new ListNode(0); dummy.next = head; // 定義 prev 和 end 結(jié)點(diǎn) ListNode prev = dummy; ListNode end = dummy; while(end.next != null) { // 以 k 個(gè)結(jié)點(diǎn)為條件，分組子鏈表 for (int i = 0; i < k && end != null; i++) end = end.next; // 不足 K 個(gè)時(shí)不處理 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 值都不會(huì)太大，所以用遞歸沒問題，當(dāng)然你也可以換成循環(huán)實(shí)現(xiàn)。對(duì)細(xì)節(jié)不了解的，可以參見《單鏈表翻轉(zhuǎn)》。

三. 小結(jié)時(shí)刻

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

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

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

單鏈表翻轉(zhuǎn)。

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

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