文章目錄
- 前言
- 基本思路
- 代碼總覽
- 舉例分析
前言
在單向連結清單的建立與周遊中，我們知道了如何建立并且周遊單向連結清單。那麼，如果要将一個連結清單進行逆轉（将連結清單的第一個元素轉為最後一個元素，第二個元素轉為倒數第二個元素，以此類推），又該如何實作呢？
說到這裡，有些博友可能會想到：建立一個臨時變量temp，并建立兩個指針P1，P2，P1指向連結清單開頭，P2指向連結清單末尾，然後通過temp變量将P1和P2指向的結點的資料域進行交換，然後将P1向後移，P2向前移，繼續交換資料域，直到全部交換。這樣必然是可行的，但我們這次的要求是：不建立臨時變量，做到連結清單逆轉。
接下來我們看看如何在不建立臨時變量的情況下将連結清單逆轉。
基本思路
單向連結清單的指針指向是從頭開始，一直指到尾。我們如果想要将一個單向連結清單進行逆轉，隻需在周遊連結清單的時候改變每個結點之間指針的指向即可，即讓單向連結清單的指針指向變成從尾指到頭，最後将逆轉後新連結清單的頭指針傳回即可。
在周遊連結清單的時候，我們是從頭開始周遊，在周遊的過程中需要時刻“記住”下一個結點的位置，否則當我們将某個結點的指針方向改變後就無法找到下一個結點，是以我們可以用一個指針先儲存下一個結點的位址，然後再改變該結點的指針方向，這樣便能找到下一個結點位置了。
代碼總覽
typedef int ElementType;//定義資料類型，可根據需要進行其他類型定義
//連結清單結點定義
typedef struct ListNode
{
ElementType Data;//資料域，存儲資料
struct ListNode* Next;//指針域，存儲下一個結點的位址
}Node, *PNode;
PNode ReverseList(PNode List)
{
PNode Old_head = List;//第一個含有資料的結點位址
PNode New_head = NULL;
while (Old_head != NULL)
{
PNode Temp = Old_head->Next;//Temp存儲下一個結點的位址
Old_head->Next = New_head;//改變指針指向
New_head = Old_head;//New_head後移
Old_head = Temp;//Old_head讀取下一個結點的位址
}
return New_head;//傳回新連結清單的第一個結點位置
} 舉例分析
僅僅看代碼可能并不能了解代碼的含義，這時我們就得舉個例子，通過畫圖來進一步了解代碼的含義。
例如，某一單向連結清單的資料為：2，3，4，5。我們要對該連結清單進行逆序，代碼執行的過程如下，其中一個長方塊代表一個結點，長方塊左半部分是資料域，右半部分是指針域，紅色線代表目前循環所進行的操作，藍色番号表示執行的先後順序。
循環還未進行時，布局如下：
當循環進行一次後，布局變為：
繼續循環：
再循環：
再來一次循環：
這時，因為Old_head為空指針，跳出循環，結果就是這樣的：
當然，這樣看着不怎麼順眼，我們可以重新排一下位置：