常見的鏈表翻轉，位元組跳動加了個條件，面試者高呼「我太難了」| 圖解算法
- 2019 年 11 月 5 日
- 筆記
本文首發自公眾號「承香墨影（ID：cxmyDev）」，歡迎關注。
一. 序
我又來講鏈表題了，這道題據說是來自位元組跳動的面試題。
為什麼說是「據說」呢？因為我也是看來的，覺得題目還是挺有意思，但是原作者給出的方案，我想了想覺得還有優化空間，就單獨拿出來講講。
就像本文的題目說的，這是一道關於鏈表翻轉的題。鏈表的翻轉，之前的文章也講了很多，例如：鏈表翻轉、鏈表兩兩翻轉、K 個一組翻轉鏈表。這些其實都是 leetcode 上的標準題，但是通常企業給出的面試題，多半會做一些變種，也就是加一些特殊的條件。
例如今天要講的這道題。
給定單鏈表的頭結點 head，實現一個調整鏈表的函數，從鏈表尾部開始，以 K 個結點為一組進行逆序翻轉，頭部剩餘結點不足一組時，不需要翻轉。（不能使用隊列或者棧作為輔助）
仔細讀題，像不像我們之前講到的 leetcode 第 25 題：K 個一組翻轉鏈表。
leetcode-25 是從頭結點開始，以 K 個結點一組進行翻轉。而位元組跳動這道題，是從尾結點開始。
只是多了一個從尾結點開始分組翻轉的條件，這道題的難度就增加了。
二. K個一組翻轉鏈表（頭條版）
2.1 其他人的解題思路
前面也說到，這道題是我看來的，當時是以一篇文章的形式發佈出來。
文章我就不發了，不過先了解一下他的解題思路，有助於我們思考。
他的思路很清晰，雖然這道題他不會解，但是 leetcode-25 這個標準的以 K 個一組翻轉鏈表的題他很熟悉。
那麼可以先將原始鏈表，進行一次「鏈表翻轉」，再進行「K 個一組翻轉鏈表」，最後再做一次「鏈表翻轉」還原鏈表，就得出了需要的結果。
ListNode revserseKGroupPlus(ListNode head, int k) { // 翻轉鏈表 head = reverseList(head); // K 個一組翻轉鏈表 head = reverseKGroup(head, k); // 翻轉鏈表 head = reverseList(head); return head; }把一個不熟悉的問題，經過簡單的轉換，變成熟悉的問題進行解決，這種思路是沒有錯的。
但是呢，有個問題–
在面試的場景中，通常來說，面試官的水平會高於面試者，那麼我們可以簡單的理解，面試就是一個不斷受挫的過程，這個過程總會被問到我們知識的邊界才會停止。
面試題只是起點，面試過程中深挖的哪些問題，才是觸摸到我們談薪資本的核心。當然這扯遠了，繼續回到本文的內容。
此時就算面試者當場寫出了解題代碼，也逃不開一個經典問題。
面試官：「還有更優的方案嗎？」
那麼這道題，有沒有更優的方案？答案當然是有的。
2.2 更優一點的方案
將鏈表先翻轉後處理，再翻轉回去，這樣並不優雅，其實只需一次以 K 個一組翻轉鏈表就可以。
再回憶一下 leetcode 第 25 題，它和這道題的差異，主要來自於，對不足一組的鏈表結點的處理。leetcode-25 是從頭結點開始處理，所以多出來的結點會在尾部，而位元組跳動這道題則正好相反，餘下的結點會在頭部。
但是它們同時也有一種特殊情況，就是 K 個一組進行分組時，這裡的 K 正好可以完整的分組，一個不多，一個不少的分成 N 組。
當鏈表結點數量正好為 K * N 時，那麼又回到了我們熟悉的 leetcode-25 題了。
如果我們先將原始結點進行處理，找出它正好可以整除 K 的起始結點 offset，將這個起始結點 offset 的子鏈表，再進行 K 個一組進行翻轉鏈表，最後把它拼接回原始鏈表，就完成了這道題。
這個過程，需要額外定義兩個結點，第一個滿足 K 個分組條件的 offset 結點，以及 offset 的前驅結點 prev 結點，prev 結點主要是用來拼接翻轉後的兩個鏈表，讓其不會出現鏈表斷裂的問題。
它們的關係如下：
這其中還涉及到一些簡單的鏈表運算，例如求鏈表的長度，這裡就不展開說了，直接上核心代碼，邏輯都在注釋里，我們先定義一個 reverseKGroupPlus() 方法。
public ListNode reverseKGroupPlus(ListNode head, int k) { if (head == null || k <= 1) return head; // 計算原始鏈表長度 int length = linkedLength(head); if (length < k) return head; // 計算 offset int offsetIndex = length % k; // 原始鏈表正好可以由 K 分為 N 組，可直接處理 if (offsetIndex == 0) { return reverseKGroup(head, k); } // 定義並找到 prev 和 offset ListNode prev = head, offset = head; while (offsetIndex > 0) { prev = offset; offset = offset.next; offsetIndex--; } // 將 offset 結點為起始的子鏈表進行翻轉，再拼接回主鏈表 prev.next = reverseKGroup(offset, k); return head; }注意當鏈表長度正好可以用 K 分為 N 組時，我們直接處理，否者才需要後續複雜的邏輯。
代碼的注釋足夠清晰了，在腦子裡過一遍代碼的執行流程應該能明白，為了幫助大家理解，我又畫了個示意圖。
假設以 head 為頭結點的鏈表長度是 10，K 為 4 時，那麼計算下來 offset Index 就是 2。
找到 prev 和 offset 結點後，就可以將以 offset 結點為頭結點的子鏈表，進行 K 個一組翻轉鏈表的操作了。
此時，head 結點為起始的鏈表，就是我們計算後的結果。
2.3 再補一些額外的代碼
這道題，還涉及到很多其他的小算法，本身 leetcode-25 就已經被定級為「困難」，位元組跳動在這道題的基礎上，又增加了難度。
為了保證解題的完整，這裡再補充一些相關代碼。
1. 計算鏈表長度
private int linkedLength(ListNode head) { int count = 0; while (head != null) { count++; head = head.next; } return count; }沒什麼好說的，一個 while 循環搞定。
2. 以 K 個一組翻轉鏈表
這道題在之前的文章中詳細講解了，這裡直接貼代碼了。
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; }對於 leetcode-25 這道題，還不太了解的可以看看之前的文章《K 個一組翻轉鏈表》。
三. 小結時刻
以上就是我解這道題的思路，可能不是最高效的，但也算是比較清晰。
在面試過程中，鏈表相關的題目可以說是高頻題。雖然企業在出題時，為了增加難度也會做一些變種，但是作為面試者，無論如何都避不開多練多寫多想。
你有更好的方案嗎？你在面試中有碰到什麼奇葩的算法題嗎？歡迎在留言區討論。
本文對你有幫助嗎？留言、轉發、收藏是最大的支持，謝謝！
公眾號後台回復成長『成長』，將會得到我準備的學習資料，也能回復『加群』，一起學習進步。
