單連結清單的逆置（翻轉）

給定一個單連結清單，我們怎麼讓它逆置呢？

我的思想是利用指針的移動來做。

當然首先我們必須考慮到一種特殊情況：這個連結清單中沒有元素或者隻有一個元素，那麼這個連結清單逆置之後的結果仍然是原連結清單，是以如果遇到這種情況，我們就可以直接傳回這個連結清單的頭指針。

除去這種特殊情況，我們來到了至少有兩個元素的連結清單的處理，首先我們需要有兩個指針pRev和pCur，令pCur指向頭結點，pRev指向pCur（頭結點）之前的節點（NULL），然後通過改變pCur的指向，使它指向pRev節點，并且還需要将指針向後移動，直到pCur指向空為止，是以我們需要一個循環來做這一系列改變指向和移動目前指針的操作。由于我們改變了pCur的指向之後再去移動pCur和pRev，就會使得pRev的移動變得相當困難，是以我們需要一個臨時變量pTemp來記錄pCur移動之前的指向，這樣我們就可以先讓pCur向後移動一個，再讓pTemp->_next指向pRev，最後将pRev移動到pTemp的位置上，這樣一次循環就搞定了。

這麼一大段文字相信大家可能會看的很懵逼，是以下面我就用幾張圖來模拟一下第一次循環的過程，相信大家看完一次循環過程就明白整個過程其中的奧妙啦。

看到這裡小夥伴們是不是瞬間有種醍醐灌頂的感覺呀，是以說呢，資料結構這部分不明白就畫畫圖，可能會有意想不到的收獲喲！

下面我就将上面所說的這些化成代碼：

Node* ReverseList(Node* pHead)     //逆置單連結清單
{
	if(pHead == NULL || pHead->_next == NULL)
		return pHead;
	
	Node* pRev = NULL;
	Node* pCur = pHead;
	while(pCur)
	{
		Node* pTemp = pCur;
		pCur = pCur->_next;
		pTemp->_next = pRev;
		pRev = pTemp;
	}
	return pRev;
}
           

如果想要驗證一下代碼的寶寶們千萬不要忘記最後銷毀節點釋放空間，必要的時候也可以列印對外連結表看看結果是否符合預期，下面我再給懶寶寶們貼上整個完整的測試代碼，可供參考喲：

#include <iostream>
using namespace std;

struct Node
{
	int _data;
	Node* _next;
	Node(int data):_data(data){}
};

Node* CreateList()     //建立連結清單
{
	Node* pHead = NULL;
	Node* n1 = new Node(1);
	Node* n2 = new Node(2);
	Node* n3 = new Node(3);
	Node* n4 = new Node(4);
	Node* n5 = new Node(5);

	pHead = n1;
	n1->_next = n2;
	n2->_next = n3;
	n3->_next = n4;
	n4->_next = n5;
	n5->_next = NULL;

	return pHead;
}

void PrintList(Node* pHead)   //正向列印連結清單
{
	if(pHead == NULL)
	{
		cout<<"連結清單為空，無法列印！！！"<<endl;
		return;
	}
	Node* pCur = pHead;
	while(pCur)
	{
		cout<<pCur->_data<<"->";
		pCur = pCur->_next;
	}
	cout<<"NULL"<<endl;
}

Node* ReverseList(Node* pHead)     //逆置單連結清單
{
	if(pHead == NULL || pHead->_next == NULL)
		return pHead;
	
	Node* pRev = NULL;
	Node* pCur = pHead;
	while(pCur)
	{
		Node* pTemp = pCur;
		pCur = pCur->_next;
		pTemp->_next = pRev;
		pRev = pTemp;
	}
	return pRev;
}

void DestroyList(Node* pHead)  //銷毀單連結清單，釋放空間
{
	while(pHead)
	{
		Node* temp = pHead;
		pHead = pHead->_next;
		delete temp;
	}
}

void FunTest()
{
	cout<<"原連結清單："<<endl;
	Node* pHead1 = CreateList();
	PrintList(pHead1);

	cout<<"逆置之後的連結清單："<<endl;
	Node* pHead2 = ReverseList(pHead1);
	PrintList(pHead2);
	DestroyList(pHead2);
}

int main()
{
	FunTest();
	return 0;
}