单链表逆置——C++实现的两种方法

方法一：

实现单链表逆置的时候，把下一节点提前保存，然后修改指向关系，再更新遍历的节点，最后更改头指针的指向和引用即可

//方法一
#include <stdio.h>

//单链表的结构体
typedef struct node
{
	int data;
	struct node* next;
}Node,*pNode;


void reverseLinkList(pNode &pListHead)				//注意使用的是引用
{
	if (pListHead == NULL || pListHead->next == NULL)    //若链表为空或者只有一个节点的情况 返回不处理
		return;
	pNode pPre = pListHead;
	pNode pCur = pListHead->next;
	pNode pNext = NULL;

	while (pCur != NULL)
	{
		//前三句的思路和交换两个数据的思路是一样的  先用一个容器保留下来
		pNext = pCur->next;	    //保存下一节点
		pCur->next = pPre;		//更改指向关系
		pPre = pCur;			//更新节点
		pCur = pNext;
	}
	pListHead->next = NULL;		//使尾节点的下一指向为NULL
	pListHead = pPre;			//更新头节点
}
void printfList(pNode pListHead)
{
	//if (pListHead == NULL)
		//return;
	pNode pCur = pListHead;
	while (pCur != NULL)
	{
		printf("%d->", pCur->data);
		pCur = pCur->next;
	}
}
int main(int argc,char* argv[])
{
	Node p5{ 5, NULL };
	Node p4{ 4, &p5 };
	Node p3{ 3, &p4 };
	Node p2{ 2, &p3 };
	Node Head{ 1, &p2 };
	pNode pHead = &Head;
	printfList(pHead);
	reverseLinkList(pHead);
	printf("逆转后\n");
	printfList(pHead);
}

思路草图如下，供参考：

方法二：采用递归的方式实现——这种方法简单一些

基本思想：在对当前结点逆置时，先递归地逆置其后继结点，然后将后继结点指向当前结点。

实现代码如下：

#include <stdio.h>

//单链表的结构体
typedef struct node
{
	int data;
	struct node* next;
}Node,*pNode;


//方法二

void reverseLinkList(pNode pCur, pNode& ListHead)
{
	if ((NULL == pCur) || (NULL == pCur->next))
	{
		ListHead = pCur;
	}
	else
	{
		pNode pNext = pCur->next;
		reverseLinkList(pNext, ListHead);					//递归逆置后继结点
		pNext->next = pCur;									//将后继结点指向当前结点。  
		pCur->next = NULL;
	}
}
void printfList(pNode pListHead)
{
	//if (pListHead == NULL)
		//return;
	pNode pCur = pListHead;
	while (pCur != NULL)
	{
		printf("%d->", pCur->data);
		pCur = pCur->next;
	}
}
int main(int argc,char* argv[])
{
	Node p5{ 5, NULL };
	Node p4{ 4, &p5 };
	Node p3{ 3, &p4 };
	Node p2{ 2, &p3 };
	Node Head{ 1, &p2 };
	pNode pHead = &Head;
	printfList(pHead);
	reverseLinkList(pHead,pHead);
	printf("逆转后\n");
	printfList(pHead);
}