連結清單翻轉的變形實戰
接下來我們來看看連結清單翻轉的變形:
變形題 1：給定一個連結清單的頭結點 head,以及兩個整數 from 和 to ,在連結清單上把第 from 個節點和第 to 個節點這一部分進行翻轉。例如：給定如下連結清單，from = 2, to = 4 head–>5–>4–>3–>2–>1 将其翻轉後，連結清單變成 head–>5—>2–>3–>4–>1
有了之前翻轉整個連結清單的解題思路，現在要翻轉部分連結清單就相對簡單多了,主要步驟如下:
1、根據 from 和 to 找到 from-1, from, to, to+1 四個結點(注意臨界條件，如果 from 從頭結點開始，則 from-1 結點為空, 翻轉後需要把 to 設定為頭結點的後繼結點， from 和 to 結點也可能超過尾結點,這兩種情況不符合條件不翻轉)。
2、對 from 到 to 的結點進行翻轉
3、将 from-1 節點指向 to 結點，将 from 結點指向 to + 1 結點
知道了以上的思路，代碼就簡單了,按上面的步驟1，2，3 實作，注釋也寫得很詳細，看以下代碼（對 from 到 to 結點的翻轉我們使用疊代翻轉，當然使用遞歸也是可以的，限于篇幅關系不展開，大家可以嘗試一下）。
/**
* 疊代翻轉 from 到 to 的結點
*/
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {
Node fromPre = null; // from-1結點
Node from = null; // from 結點
Node to = null; // to 結點
Node toNext = null; // to+1 結點
// 步驟 1：找到 from-1, from, to, to+1 這四個結點
Node tmp = head.next;
int curIndex = 1; // 頭結點的index為1
while (tmp != null) {
if (curIndex == fromIndex-1) {
fromPre = tmp;
} else if (curIndex == fromIndex) {
from = tmp;
} else if (curIndex == toIndex) {
to = tmp;
} else if (curIndex == toIndex+1) {
toNext = tmp;
}
tmp = tmp.next;
curIndex++;
}
if (from == null || to == null) {
// from 或 to 都超過尾結點不翻轉
throw new Exception("不符合條件");
}
// 步驟2：以下使用循環疊代法翻轉從 from 到 to 的結點
Node pre = from;
Node cur = pre.next;
while (cur != toNext) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 步驟3：将 from-1 節點指向 to 結點（如果從 head 的後繼結點開始翻轉，則需要重新設定 head 的後繼結點），将 from 結點指向 to + 1 結點
if (fromPre != null) {
fromPre.next = to;
} else {
head.next = to;
}
from.next = toNext;
} 變形題 2：給出一個連結清單，每 k 個節點一組進行翻轉，并傳回翻轉後的連結清單。k 是一個正整數，它的值小于或等于連結清單的長度。如果節點總數不是 k 的整數倍，那麼将最後剩餘節點保持原有順序。
示例 : 給定這個連結清單：head–>1->2->3->4->5 當 k = 2 時，應當傳回: head–>2->1->4->3->5 當 k = 3 時，應當傳回: head–>3->2->1->4->5 說明 :
- 你的算法隻能使用常數的額外空間。
- 你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
隻要我們能找到翻一組 k 個結點的方法，問題就解決了（之後隻要重複對 k 個結點一組的連結清單進行翻轉即可）。
接下來，我們以以下連結清單為例
來看看怎麼翻轉 3 個一組的連結清單（此例中 k = 3）
- 首先，我們要記錄 3 個一組這一段連結清單的前繼結點,定義為 startKPre,然後再定義一個 step, 從這一段的頭結點 (1）開始周遊 2 次，找出這段連結清單的起始和終止結點，如下圖示
- 找到 startK 和 endK 之後，根據之前的疊代翻轉法對 startK 和 endK 的這段連結清單進行翻轉
- 然後将 startKPre 指向 endK,将 startK 指向 endKNext，即完成了對 k 個一組結點的翻轉。
知道了一組 k 個怎麼翻轉，之後隻要重複對 k 個結點一組的連結清單進行翻轉即可，對照圖示看如下代碼應該還是比較容易了解的
/**
* 每 k 個一組翻轉連結清單
* @param k
*/
public void iterationInvertLinkedListEveryK(int k) {
Node tmp = head.next;
int step = 0; // 計數，用來找出首結點和尾結點
Node startK = null; // k個一組連結清單中的頭結點
Node startKPre = head; // k個一組連結清單頭結點的前置結點
Node endK; // k個一組連結清單中的尾結點
while (tmp != null) {
// tmp 的下一個節點,因為由于翻轉，tmp 的後繼結點會變,要提前儲存
Node tmpNext = tmp.next;
if (step == 0) {
// k 個一組連結清單區間的頭結點
startK = tmp;
step++;
} else if (step == k-1) {
// 此時找到了 k 個一組連結清單區間的尾結點（endK）,對這段連結清單用疊代進行翻轉
endK = tmp;
Node pre = startK;
Node cur = startK.next;
if (cur == null) {
break;
}
Node endKNext = endK.next;
while (cur != endKNext) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 翻轉後此時 endK 和 startK 分别是是 k 個一組連結清單中的首尾結點
startKPre.next = endK;
startK.next = endKNext;
// 目前的 k 個一組翻轉完了，開始下一個 k 個一組的翻轉
startKPre = startK;
step = 0;
} else {
step++;
}
tmp = tmpNext;
}
} 時間複雜度是多少呢，對連結清單從頭到尾循環了 n 次，同時每 k 個結點翻轉一次，可以認為總共翻轉了 n 次，是以時間複雜度是O(2n),去掉常數項，即為 O(n)。注：這題時間複雜度比較誤認為是O(k * n),實際上并不是每一次連結清單的循環都會翻轉連結清單，隻是在循環連結清單元素每 k 個結點的時候才會翻轉
變形題 3:變形 2 針對的是順序的 k 個一組翻轉，那如何逆序 k 個一組進行翻轉呢
例如：給定如下連結清單， head–>1–>2–>3–>4–>5 逆序 k 個一組翻轉後，連結清單變成
head–>1—>3–>2–>5–>4 （k = 2 時）
這道題是位元組跳動的面試題，确實夠變态的，順序 k 個一組翻轉都已經屬于 hard 級别了，逆序 k 個一組翻轉更是屬于 super hard 級别了，不過其實有了之前知識的鋪墊，應該不難，隻是稍微變形了一下，隻要對連結清單做如下變形即可
代碼的每一步其實都是用了我們之前實作好的函數，是以我們之前做的每一步都是有伏筆的哦！就是為了解決位元組跳動這道終極面試題！
/**
* 逆序每 k 個一組翻轉連結清單
* @param k
*/
public void reverseIterationInvertLinkedListEveryK(int k) {
// 先翻轉連結清單
iterationInvertLinkedList();
// k 個一組翻轉連結清單
iterationInvertLinkedListEveryK(k);
// 再次翻轉連結清單
iterationInvertLinkedList();
} 由此可見，掌握基本的連結清單翻轉非常重要！難題多是在此基礎了做了相應的變形而已
總結
本文詳細講解了連結清單與數組的本質差別，相信大家對兩者的差別應該有了比較深刻的認識，尤其是程式局部性原理，相信大家看了應該會眼前一亮，之後通過對連結清單的翻轉由淺入深地介紹，相信之後的連結清單翻轉對大家應該不是什麼難事了，不過建議大家親自實作一遍文中的代碼哦，這樣印象會更深刻一些！
有時候看起來思路是這麼一回事，但真正操作起來還是會有不少坑，紙上得來終覺淺，絕知此事要躬行！
來源 | 五分鐘學算法
作者 | 程式員小吳