单链表的逆置（翻转）

给定一个单链表，我们怎么让它逆置呢？

我的思想是利用指针的移动来做。

当然首先我们必须考虑到一种特殊情况：这个链表中没有元素或者只有一个元素，那么这个链表逆置之后的结果仍然是原链表，所以如果遇到这种情况，我们就可以直接返回这个链表的头指针。

除去这种特殊情况，我们来到了至少有两个元素的链表的处理，首先我们需要有两个指针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;
}