1.8 如何把鏈表以K個結點為一組進行翻轉

【出自MT筆試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

K鏈表翻轉是指把每K個相鄰的結點看成一組進行翻轉，如果剩余結點不足K個，則保持不變。假設給定鏈表1→2→3→4→5→6→7和一個數K，如果K的值為2，那么翻轉后的鏈表為2→1→4→3→6→5→7。如果K的值為3，那么翻轉后的鏈表為3→2→1→6→5→4→7。

分析與解答：

主要思路為：首先把前K個結點看成一個子鏈表，采用前面介紹的方法進行翻轉，把翻轉后的子鏈表鏈接到頭結點后面，然后把接下來的K個結點看成另外一個單獨的鏈表進行翻轉，把翻轉后的子鏈表鏈接到上一個已經完成翻轉子鏈表的后面。具體實現方法如下圖所示。

在上圖中，以K=3為例介紹具體實現的方法：

1）首先設置pre指向頭結點，然后讓begin指向鏈表第一個結點，找到從begin開始第K=3個結點end。

2）為了采用1.1節中鏈表翻轉的算法，需要使end.next=null，在此之前需要記錄下end指向的結點，用pNext來記錄。

3）使end.next=null，使得從begin到end為一個單獨的子鏈表，從而可以對這個子鏈表采用1.1節介紹的方法進行翻轉。

4）對以begin為第一個結點，end為尾結點所對應的K=3個結點進行翻轉。

5）由于翻轉后子鏈表的第一個結點從begin變為end，因此，執行pre.next=end，把翻轉后的子鏈表鏈接起來。

6）把鏈表中剩余的還未完成翻轉的子鏈表鏈接到已完成翻轉的子鏈表后面（主要是針對剩余的結點的個數小于K的情況）。

7）讓pre指針指向已完成翻轉的鏈表的最后一個結點。

8）讓begin指針指向下一個需要被翻轉的子鏈表的第一個結點（通過begin=pNext來實現）。

接下來可以反復使用步驟（1）～（8）對鏈表進行翻轉。

實現代碼如下：

程序的運行結果為

運行結果分析：

由于K=3，因此，鏈表可以分成三組（1 2 3）、（4 5 6）、（7）。對（1 2 3）翻轉后變為（3 2 1），對（4 5 6）翻轉后變為（6 5 4）。由于（7）這個子鏈表只有一個結點（小于3個），因此不進行翻轉，所以翻轉后的鏈表就變為3→2→1→6→5→4→7。

算法性能分析：

這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O（n）。另外，由于只需要幾個指針變量來保存結點的地址信息，因此，空間復雜度為O（1）。