1.1 如何實現鏈表的逆序

難度系數：★★★☆☆

被考查系數：★★★★☆

題目描述：

給定一個帶頭結點的單鏈表，請將其逆序。即如果單鏈表原來為head->1->2->3->4->5->6->7，則逆序后變為head->7->6->5->4->3->2->1。

分析與解答：

由于單鏈表與數組不同，單鏈表中每個結點的地址都存儲在其前驅結點的指針域中，因此，對單鏈表中任何一個結點的訪問只能從鏈表的頭指針開始進行遍歷。在對鏈表的操作過程中，需要特別注意在修改結點指針域的時候，記錄下后繼結點的地址，否則會丟失后繼結點。

方法一：就地逆序

主要思路為：在遍歷鏈表的時候，修改當前結點指針域的指向，讓其指向它的前驅結點。為此需要用一個指針變量來保存前驅結點的地址。此外，為了在調整當前結點指針域的指向后還能找到后繼結點，還需要另外一個指針變量來保存后繼結點的地址，在所有的結點都被保存好以后就可以直接完成指針的逆序了。除此之外，還需要特別注意對鏈表首尾結點的特殊處理。具體實現方式如下圖所示。

在上圖中，假設當前已經遍歷到cur結點，由于它所有的前驅結點都已經完成了逆序操作，因此，只需要使cur.next=pre即可完成逆序操作，在此之前為了能夠記錄當前結點的后繼結點的地址，需要用一個額外的指針next來保存后繼結點的信息，通過上圖（1）～（4）四步把實線的指針調整為虛線的指針就可以完成當前結點的逆序；當前結點完成逆序后，通過向后移動指針來對后續的結點用同樣的方法進行逆序操作。實現代碼如下：

程序的運行結果為

算法性能分析：

以上這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(n)，其中，n為鏈表的長度。但是需要常數個額外的變量來保存當前結點的前驅結點與后繼結點，因此，空間復雜度為O(1)。

方法二：遞歸法

假定原鏈表為1->2->3->4->5->6->7，遞歸法的主要思路為：先逆序除第一個結點以外的子鏈表（將1->2->3->4->5->6->7變為1->7->6->5->4->3->2），接著把結點1添加到逆序的子鏈表的后面（1->2->3->4->5->6->7 變為 7->6->5->4->3->2->1）。同理，在逆序鏈表 2->3->4->5->6->7時，也是先逆序子鏈表 3->4->5->6->7（逆序為2->7->6->5->4->3），接著實現鏈表的整體逆序（2->7->6->5->4->3 轉換為7->6->5->4->3->2）。實現代碼如下：

算法性能分析：

由于遞歸法也只需要對鏈表進行一次遍歷，因此，算法的時間復雜度也為O(n)，其中， n為鏈表的長度。遞歸法的主要優點是：思路比較直觀，容易理解，而且也不需要保存前驅結點的地址；缺點是：算法實現的難度較大，此外，由于遞歸法需要不斷地調用自己，需要額外的壓棧與彈棧操作，因此，與方法一相比性能會有所下降。

方法三：插入法

插入法的主要思路為：從鏈表的第二個結點開始，把遍歷到的結點插入到頭結點的后面，直到遍歷結束。假定原鏈表為node->1->2->3->4->5->6->7，在遍歷到2的時候，將其插入到頭結點后，鏈表變為node->2->1->3->4->5->6->7，同理將后序遍歷到的所有結點都插入到頭結點head后，就可以實現鏈表的逆序。實現代碼如下：

算法性能分析：

以上這種方法也只需要對單鏈表進行一次遍歷，因此，時間復雜度為O(n)，其中，n為鏈表的長度。與方法一相比，這種方法不需要保存前驅結點的地址，與方法二相比，這種方法不需要遞歸地調用，效率更高。

引申：（1）對不帶頭結點的單鏈表進行逆序。

（2）從尾到頭輸出鏈表。

分析與解答：

對不帶頭結點的單鏈表的逆序讀者可以自己練習（方法二已經實現了遞歸的方法），這里主要介紹單鏈表逆向輸出的方法。

方法一：就地逆序+順序輸出

首先對鏈表進行逆序，然后順序輸出逆序后的鏈表。這種方法的缺點是改變了鏈表原來的結構。

方法二：逆序+順序輸出

申請新的存儲空間，對鏈表進行逆序，然后順序輸出逆序后的鏈表。逆序的主要思路為：每當遍歷到一個結點的時候，申請一塊新的存儲空間來存儲這個結點的數據域，同時把新結點插入到新鏈表的頭結點后。這種方法的缺點是需要申請額外的存儲空間。

方法三：遞歸輸出

遞歸輸出的主要思路為：先輸出除當前結點外的后繼子鏈表，然后輸出當前結點，假如鏈表為：1->2->3->4->5->6->7，那么先輸出2->3->4->5->6->7，再輸出1。同理，對于鏈表2->3->4->5->6->7，也是先輸出3->4->5->6->7，接著輸出2，直到遍歷到鏈表的最后一個結點7的時候會輸出結點7，然后遞歸地輸出6，5，…，1。實現代碼如下：

程序的運行結果為

算法性能分析：

以上這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(n)，其中，n為鏈表的長度。