1.7 如何把鏈表相鄰元素翻轉

【出自TX筆試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

把鏈表相鄰元素翻轉，如給定鏈表為1→2→3→4→5→6→7，則翻轉后的鏈表變為2→1→4→3→6→5→7。

分析與解答：

方法一：交換值法

最容易想到的方法就是交換相鄰兩個結點的數據域，這種方法由于不需要重新調整鏈表的結構，因此比較容易實現，但是這種方法并不是考官所期望的解法。

方法二：就地逆序

主要思路：通過調整結點指針域的指向來直接調換相鄰的兩個結點。如果單鏈表恰好有偶數個結點，那么只需要將奇偶結點對調即可，如果鏈表有奇數個結點，那么只需要將除最后一個結點外的其他結點進行奇偶對調即可。為了便于理解，下圖給出了其中第一對結點對調的方法。

在上圖中，當前遍歷到結點cur，通過步驟（1）～（6）用虛線的指針來代替實線的指針實現相鄰結點的逆序。其中，步驟（1）～（4）實現了前兩個結點的逆序操作，步驟（5）和（6）向后移動指針，接著可以采用同樣的方式實現后面兩個相鄰結點的逆序操作。實現代碼如下：

程序的運行結果為

上例中，由于鏈表有奇數個結點，因此，鏈表前三對結點相互交換，而最后一個結點保持在原來的位置。

算法性能分析：

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