來源公眾號：苦逼的碼農作者：帥地
前幾天有個朋友去面試位元組跳動，面試官問了他一道鍊表相關的算法題，不過他一時之間沒做出來，就來問了我一下，感覺這道題還不錯，拿來講一講。
這其實是一道變形的鍊表反轉題，大致描述如下
給定一個單鍊表的頭節點 head,實現一個調整單鍊表的函數，使得每K個節點之間為一組進行逆序，並且從鍊表的尾部開始組起，頭部剩餘節點數量不夠一組的不需要逆序。（不能使用隊列或者棧作為輔助）
例如：鍊表:1->2->3->4->5->6->7->8->, K = 3。那麼 6->7->8，3->4->5，1->2各位一組。調整後：1->2->5->4->3->8->7->6->。其中 1，2不調整，因為不夠一組。
這道題的難點在於，是從鍊表的尾部開始組起的，而不是從鍊表的頭部，如果是頭部的話，那我們還是比較容易做的，因為你可以遍歷鍊表，每遍歷 k 個就拆分為一組來逆序。但是從尾部的話就不一樣了，因為是單鍊表，不能往後遍歷組起。不過這道題肯定是用遞歸比較好做，對遞歸不大懂的建議看我之前寫的一篇文章為什麼你學不會遞歸？告別遞歸，談談我的一些經驗，這篇文章寫了關於遞歸的一些套路。
在做這道題之前，我們不仿先來看看如果從頭部開始組起的話，應該怎麼做呢？例如：鍊表:1->2->3->4->5->6->7->8->, K = 3。調整後：3->2->1->6->5->4->7->8->。其中 7，8不調整，因為不夠一組。
對於這道題，如果你不知道怎麼逆序一個單鍊表，那麼可以看一下我之前寫的如何優雅著反轉單鍊表
這道題我們可以用遞歸來實現，假設方法reverseKNode的功能是將單鍊表的每K個節點之間逆序(從頭部開始組起的哦);reverse方法的功能是將一個單鍊表逆序。
那麼對於下面的這個單鍊表，其中 K = 3。
我們把前K個節點與後面的節點分割出來：
temp指向的剩餘的鍊表，可以說是原問題的一個子問題。
我們可以調用reverseKNode方法將temp指向的鍊表每K個節點之間進行逆序。
再調用reverse方法把head指向的那3個節點進行逆序，結果如下：
再次聲明，如果對這個遞歸看不大懂的，建議看下我那篇遞歸的文章
接著，我們只需要把這兩部分給連接起來就可以了。最後的結果如下：
代碼如下：
//k個為一組逆序
public ListNode reverseKGroup(ListNode head, int k) {
ListNode temp = head;
for (int i = 1; i < k && temp != ; i++) {
temp = temp.next;
}
//判斷節點的數量是否能夠湊成一組
if(temp == )
return head;
ListNode t2 = temp.next;
temp.next = ;
//把當前的組進行逆序
ListNode newHead = reverseList(head);
//把之後的節點進行分組逆序
ListNode newTemp = reverseKGroup(t2, k);
// 把兩部分連接起來
head.next = newTemp;
return newHead;
}
//逆序單鍊表
private static ListNode reverseList(ListNode head) {
if(head == || head.next == )
return head;
ListNode result = reverseList(head.next);
head.next.next = head;
head.next = ;
return result;
}
這兩道題可以說是及其相似的了，只是一道從頭部開始組起，這道從頭部開始組起的，也是 leetcode 的第 25 題。而面試的時候，經常會進行變形，例如這道位元組跳動的題，它變成從尾部開始組起，可能你一時之間就不知道該怎麼弄了。當然，可能有人一下子就反應出來，把他秒殺了。
其實這道題很好做滴，你只需要先把單鍊表進行一次逆序，逆序之後就能轉化為從頭部開始組起了，然後按照我上面的解法，處理完之後，把結果再次逆序即搞定。兩次逆序相當於沒逆序。
例如對於鍊表（其中 K = 3）
我們把它從尾部開始組起，每 K 個節點為一組進行逆序。
步驟如下
1、先進行逆序
逆序之後就可以把問題轉化為從頭部開始組起，每 K 個節點為一組進行逆序。
2、處理後的結果如下
3、接著在把結果逆序一次，結果如下
代碼如下
public ListNode solve(ListNode head, int k) {
// 調用逆序函數
head = reverse(head);
// 調用每 k 個為一組的逆序函數（從頭部開始組起）
head = reverseKGroup(head, k);
// 在逆序一次
head = reverse(head);
return head;
}
類似於這種需要先進行逆序的還要兩個鍊表相加，這道題位元組跳動的筆試題也有出過，如下圖的第二題
這道題就需要先把兩個鍊表逆序，再節點間相加，最後在合併了。
關於鍊表的算法題，在面試的時候聽說是挺常考的，大家可以多注意注意，遇到不錯的鍊表算法題，也歡迎扔給我勒。