原文：[https://juejin.im/post/5d4f76325188253b49244dd0](https://juejin.im/post/5d4f76325188253b49244dd0) ### 題目 這其實是一道**變形**的鏈表反轉題，大致描述如下 給定一個單鏈表的頭節點 head,實現一個調整單鏈表的函數，使得每K個節點之間為一組進行逆序，**并且從鏈表的尾部開始組起**，頭部剩余節點數量不夠一組的不需要逆序。（不能使用隊列或者棧作為輔助） *例如*： 鏈表:`1->2->3->4->5->6->7->8->null, K = 3。`那么` 6->7->8，3->4->5，1->2`各位一組。調整后：`1->2->5->4->3->8->7->6->null。`其中 1，2不調整，因為不夠一組。 ### 解答 這道題的難點在于，是從鏈表的尾部開始組起的，而不是從鏈表的**頭部**，如果是頭部的話，那我們還是比較容易做的，因為你可以遍歷鏈表，每遍歷 k 個就拆分為一組來逆序。但是從尾部的話就不一樣了，因為是單鏈表，不能往后遍歷組起。不過這道題肯定是用遞歸比較好做，對遞歸不大懂的建議看我之前寫的一篇文章[為什么你學不會遞歸？告別遞歸，談談我的一些經驗](https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2FmJ_jZZoak7uhItNgnfmZvQ "https://mp.weixin.qq.com/s/mJ_jZZoak7uhItNgnfmZvQ")，這篇文章寫了關于遞歸的一些套路。 ### 先做一道類似的反轉題 在做這道題之前，我們不仿先來看看**如果從頭部開始組起的話**，應該怎么做呢？例如：鏈表:1->2->3->4->5->6->7->8->null, K = 3。調整后：3->2->1->6->5->4->7->8->null。其中 7，8不調整，因為不夠一組。 對于這道題，如果你不知道怎么逆序一個單鏈表，那么可以看一下我之前寫的[如何優雅著反轉單鏈表](https://link.juejin.cn?target=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2FWNO3KNhS6oU7rUvCNEGw8g "https://mp.weixin.qq.com/s/WNO3KNhS6oU7rUvCNEGw8g") 這道題我們可以用遞歸來實現，假設方法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 != null; i++) { temp = temp.next; } //判斷節點的數量是否能夠湊成一組 if(temp == null) return head; ListNode t2 = temp.next; temp.next = null; //把當前的組進行逆序 ListNode newHead = reverseList(head); //把之后的節點進行分組逆序 ListNode newTemp = reverseKGroup(t2, k); // 把兩部分連接起來 head.next = newTemp; return newHead; } //逆序單鏈表 private static ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode result = reverseList(head.next); head.next.next = head; head.next = null; 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; } 復制代碼 ~~~ 類似于這種需要先進行逆序的還要兩個鏈表相加，這道題字節跳動的筆試題也有出過，如下圖的第二題  這道題就需要先把兩個鏈表逆序，再節點間相加，最后在合并了。 ### 總結 關于鏈表的算法題，在面試的時候聽說是挺常考的，大家可以多注意注意，遇到不錯的鏈表算法題，也歡迎扔給我勒。 作者：帥地 鏈接：https://juejin.cn/post/6844903910386171912 來源：稀土掘金 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。