反轉單向鏈表的四種實現（遞歸與非遞歸，C++）

單項鍊表的反轉指的是這樣一類問題：給定一個單項鍊表的頭指針 head，寫一個算法，將其反轉，並返回新的頭指針 head’。

本文給出了這一問題的兩種解法，分別是遞歸解法和非遞歸解法。

遞歸解法一

遞歸解法一的思路如下。

定義一個方法 reserve1inner (node *element, node *prev)，用來反轉指定的節點。

這個方法使用如下辦法執行：先反轉這個節點的後續節點，然後再反轉自己。

所謂「反轉自己」，就是指將自己的next字段的值改成prev（上一個節點的指針）的值。也就是說，把本來指向後面一個節點地址的next字段改為指向前一個節點地址的prev字段。

這個思路里有兩點需要注意：

為什麼要提供 prev 參數？ 單項鍊表中是隻有後續節點的地址的，因此當反轉 element 的時候，必須手工提供 prev 參數。通過遞歸，這個參數正好由其前一項調用時提供。第一次調用時，這個參數由 reserve1 函數直接提供 nullptr。
如何得到新的 head’的值？head’的值只有當遍歷到最後一個節點時才會獲得，因此需要回傳。所以將遞歸方法增加了一個返回值，返回值就定義為新的head’的指針值。獲取這個值的方法是，直接返回下一層遞歸的值即可，除非，已經是最後一層，此時應返回自身。

遞歸解法二

遞歸解法二的思路如下。

定義一個方法 reserve (node *element)，用來反轉指定的節點。

這個方法和解法一不同：直觀上看少了一個參數 prev，本質上看，函數的定義不同。第二個解法其實是一種「拼接」的算法：將老的鏈表扭斷，逐步拼到新的鏈表上去。（可以參考非遞歸解法二的說明）第一個解法要把它和上一個相連（prev），第二個解法只把它自己反轉完，前一個節點直接設置為 nullptr。也就是說，在這個方法執行完後，如果element 不是第一個節點，那麼這個節點會和它前面的節點斷開。

下面是本解法的主要步驟：

如果 element 是唯一的元素（element 的下一個為空），則直接返回 element。（element 就是它本身的頭指針）
如果不是，那麼先反轉 element 的 next，並將返回值保存為 ptrHeadNext（反轉之後，其實這裡面存儲的是原來最後一個的指針）。
將 element 拼接在新反轉的元素之後，利用 ptrHeadNext。（此處目前其實存儲的是反轉後尾部）

非遞歸解法一

非遞歸解法的思路是遍歷。

針對每一個節點，指針為 ptrCurrent，都進行一次處理。
處理的時候，都是將這個節點的next設置為上一次處理的 ptrCurrent（此時已經保存為 prev）。
初始化的時候，先將第一個 ptrCurrent 反轉後設置的 prev 定義為 nullptr。

非遞歸解法二

我們也可以有一種更清晰的思路來求解。主要思想是，重新拼接新的鏈表（而不是直接修改老鏈表）。也就是說，我們執行如下步驟：

創建一個反轉後的鏈表，設置其頭為ptrReserved。
每次都從老的鏈表裡，取出第一個元素，並加入到新鏈表的第一個的位置（此步完成了反轉）。
直到所有元素都被加入到 ptrReserved 中。

針對每一個節點，指針為 ptrCurrent，都進行一次處理。
處理的時候，都是將這個節點的next設置為上一次處理的 ptrCurrent（此時已經保存為 prev）。
初始化的時候，先將第一個 ptrCurrent 反轉後設置的 prev 定義為 nullptr。

註釋

nullptr 是 C++11 標準中新定義的「空指針」類型，然而目前很多編譯器還不能識別。nullptr 非常好用，因為它很好地區分了 0 和空指針這兩種不同的值（其實從本質上來說，它本是一種值）。以往使用的 NULL，null 等並不是 C++ 標準，而 nullptr 的到來很好的解決了這個問題。目前，也可以使用 define 宏來模擬。（但這並不是全等的模擬，具體請參考 C++11 的相關定義。）
注意到在遞歸的 reserve1inner 算法中，返回值前增加了一個 typename。這是 C++ 標準規定的反歧義語法，當使用模板類的嵌入類型時，必須增加 typename 關鍵字才能當作類型，否則會當作成員變量。當然，你也可以使用 typedef 去掉討厭的 typename。

實現

下面分別是兩種解法的實現代碼（第一個是遞歸解法1，第二個是非遞歸解法1）。（代碼中所引用的 ceeji::stack 類型的定義見這裡。在本文中 stack 沒有意義，有意義的只是其中的鏈表而已。）

template void stack::reserve1() {
	this->head = reserve1inner(this->head, nullptr);
}

template typename stack::node* stack::reserve1inner(stack::node *element, stack::node *prev) {
	node *ret;
	if (element->next != nullptr) {
		ret = reserve1inner(element->next, element);
	}
	else
		ret = element;

	element->next = prev;

	return ret;
}

template void stack::reserve2() {
	node *ptrCurrent = this->head;
	node *prev = nullptr, *next;

	while (ptrCurrent != nullptr) {
		next = ptrCurrent->next;
		ptrCurrent->next = prev;
		prev = ptrCurrent;

		ptrCurrent = next;
	}

	this->head = prev;
}

遞歸解法一

遞歸解法二

非遞歸解法一

非遞歸解法二

註釋

實現

猜你喜歡