前幾天有個小伙伴去面試字節(jié)跳動，面試官問了他一道鏈表相關(guān)的算法題，不過他一時之間沒做出來，就來問了我一下，感覺這道題還不錯，拿來講一講。

[[275586]]

01 題目

這其實是一道變形的鏈表反轉(zhuǎn)題，大致描述如下：

給定一個單鏈表的頭節(jié)點 head，實現(xiàn)一個調(diào)整單鏈表的函數(shù)，使得每K個節(jié)點之間為一組進行逆序，并且從鏈表的尾部開始組起，頭部剩余節(jié)點數(shù)量不夠一組的不需要逆序。(不能使用隊列或者棧作為輔助)。

例如：

• 鏈表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一組。調(diào)整后：1->2->5->4->3->8->7->6->null。其中 1，2不調(diào)整，因為不夠一組。

02 解答

這道題的難點在于，是從鏈表的尾部開始組起的，而不是從鏈表的頭部，如果是頭部的話，那我們還是比較容易做的，因為你可以遍歷鏈表，每遍歷 k 個就拆分為一組來逆序。但是從尾部的話就不一樣了，因為是單鏈表，不能往后遍歷組起，不過這道題肯定是用遞歸比較好做。

先做一道類似的反轉(zhuǎn)題

在做這道題之前，我們不仿先來看看如果從頭部開始組起的話，應(yīng)該怎么做呢?例如：鏈表:1->2->3->4->5->6->7->8->null, K = 3。調(diào)整后：3->2->1->6->5->4->7->8->null。其中 7，8不調(diào)整，因為不夠一組。

這道題我們可以用遞歸來實現(xiàn)，假設(shè)方法reverseKNode()的功能是將單鏈表的每K個節(jié)點之間逆序(從頭部開始組起的哦);reverse()方法的功能是將一個單鏈表逆序。

那么對于下面的這個單鏈表，其中 K = 3。

我們把前K個節(jié)點與后面的節(jié)點分割出來：

temp指向的剩余的鏈表，可以說是原問題的一個子問題。我們可以調(diào)用reverseKNode()方法將temp指向的鏈表每K個節(jié)點之間進行逆序。再調(diào)用reverse()方法把head指向的那3個節(jié)點進行逆序，結(jié)果如下：

接著，我們只需要把這兩部分給連接起來就可以了。最后的結(jié)果如下：

代碼如下：

回到本題

這兩道題可以說是及其相似的了，只是一道從頭部開始組起，這道從頭部開始組起的，也是 leetcode 的第 25 題。而面試的時候，經(jīng)常會進行變形，例如這道字節(jié)跳動的題，它變成從尾部開始組起，可能你一時之間就不知道該怎么弄了。當然，可能有人一下子就反應(yīng)出來，把他秒殺了。

其實這道題很好做滴，你只需要先把單鏈表進行一次逆序，逆序之后就能轉(zhuǎn)化為從頭部開始組起了，然后按照我上面的解法，處理完之后，把結(jié)果再次逆序即搞定。兩次逆序相當于沒逆序。

例如對于鏈表(其中 K = 3)

我們把它從尾部開始組起，每 K 個節(jié)點為一組進行逆序。步驟如下：

① 先進行逆序

逆序之后就可以把問題轉(zhuǎn)化為從頭部開始組起，每 K 個節(jié)點為一組進行逆序。

② 處理后的結(jié)果如下：

③ 接著在把結(jié)果逆序一次，結(jié)果如下：

代碼如下：

類似于這種需要先進行逆序的還要兩個鏈表相加，這道題字節(jié)跳動的筆試題也有出過，如下圖的第二題：

這道題就需要先把兩個鏈表逆序，再節(jié)點間相加，最后在合并了。

03 總結(jié)

關(guān)于鏈表的算法題，在面試的時候聽說是挺常考的，大家可以多注意注意。如果你覺得這篇內(nèi)容對你挺有啟發(fā)，那就點個贊唄~