c语言实现单链表的反转_单链表的就地逆转

        在c语言中，数组可以反转，字符串也可以逆序，因此链表也是可以进行反转的，反转链表是一个很经典的问题，但是其思路其实很简单。比如给一个单链表头节点plist，让plist的链表进行如下的反转：

         从上图分析可得：反转后，原先链表中的尾节点5变成了头节点，原先链表中的头节点1变成了尾节点。这里有两种方法可以实现反转链表。

方法一（3指针移动法）

        顾名思义就是创建3个指针用于维护该链表，其中第一、第二个指针用于改变节点的指向方向，第三个指针用来标记位置、记住位置。

        示意图如下：

        如此按上图的逻辑不断重复，直到n1指向最后一个节点，表明所有节点已经改变了指向，则n1指向的节点成为了反转之后的链表的头节点。

        根据上图信息，以n3为空作为结束标志时，链表还差最后一步完成反转，即：5指向4还未完成反转。若以n1为空作为结束标志时，则无法找到反转之后的头节点。因此可以让n2为空的时候作为结束反转的标志。

        代码实现和测试结果如下：

#include<stdio.h>
#include<stdlib.h>
 
typedef struct ListNode //创建节点结构体
{
	int data;
	struct ListNode *next;
}LNode;
 
LNode* reverseList(LNode* head)//反转函数
{
	 if(head==NULL)//如果是空链表则返回空即可
	     return NULL;
 
	 LNode* n1=NULL;//定义指针n1指向空
	 LNode* n2=head;//定义指针n2指向头节点
	 LNode* n3=head->next;//定义指针n3指向头节点的下一个节点
 
	 while(n2!=NULL)//以n2不为空为循环条件
	 {
	     n2->next=n1;//n2指向的节点指向n1
	     n1=n2;//移动n1至n2处
	     n2=n3;//移动n2至n3处
	     if(n3!=NULL)//如果n3已经为空则不能继续移动，否则会出现对空指针解引用的问题
	         n3=n3->next;//移动n3
	 }
	 return n1;//返回n1，即返回反转后链表的头节点
}
 
void Print(LNode* phead)//打印函数
{
	LNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");//模拟链表最后指向的是NULL
}
 
 
int main()
{
	LNode* n1 = (LNode*)malloc(sizeof(LNode));//创建4个节点，为了测试反转链表函数
	LNode* n2 = (LNode*)malloc(sizeof(LNode));
	LNode* n3 = (LNode*)malloc(sizeof(LNode));
	LNode* n4 = (LNode*)malloc(sizeof(LNode));
 
	LNode* plist = n1;//指向头节点的头指针plist
	n1->data = 1;//给每个节点都赋值
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
 
	n1->next = n2;//手动构建链表
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	
	printf("逆置前：");
	Print(plist);//打印反转之前的链表
	printf("\n");
 
	LNode* newlist=reverseList(plist);//调用反转链表函数
 
	printf("逆置后：");
	Print(newlist);//打印反转之后的链表
 
	return 0;
}

        输出结果：

方法二（节点移动法）

        该方法是将链表中的节点一个一个的”拿下来“，放到新的头节点中，类似于头插法。

        示意图：

        最后指针newhead会指向节点5，则节点5就是反转后链表的头节点，当cur指针为空时，表示整个反转过程已经完成。

        代码实现和测试结果如下：

#include<stdio.h>
#include<stdlib.h>
 
typedef struct ListNode //创建节点结构体
{
	int data;
	struct ListNode* next;
}LNode;
 
LNode* reverseList(LNode* head)//反转函数
{
	LNode* rhead = NULL;//新头指针
	LNode* cur = head;//cur用于移动节点至新头指针处
	LNode* next = NULL;//next用于记住位置
 
	while (cur!=NULL)//当cur为空时出循环
	{
		next = cur->next;//更新next的位置
		cur->next = rhead;//将cur指向的节点“移动到”rhead处
		rhead = cur;//更新头指针rhead的指向
		cur = next;//更新cur的位置至next处，即迭代
 
	}
	return rhead;//返回新的头指针也就是反转后链表的头节点地址
}
 
void Print(LNode* phead)//打印函数
{
	LNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");//模拟链表最后指向的是NULL
}
 
 
int main()
{
	LNode* n1 = (LNode*)malloc(sizeof(LNode));//创建4个节点，为了测试反转链表函数
	LNode* n2 = (LNode*)malloc(sizeof(LNode));
	LNode* n3 = (LNode*)malloc(sizeof(LNode));
	LNode* n4 = (LNode*)malloc(sizeof(LNode));
 
	LNode* plist = n1;//指向头节点的头指针plist
	n1->data = 1;//给每个节点都赋值
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
 
	n1->next = n2;//手动构建链表
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
 
	printf("逆置前：");
	Print(plist);//打印反转之前的链表
	printf("\n");
 
	LNode* newlist = reverseList(plist);//调用反转链表函数
 
	printf("逆置后：");
	Print(newlist);//打印反转之后的链表
 
	return 0;
}

        运行结果：

 结语：

        从以上两个方法的运行结果来看，两种方法都可以实现反转链表的功能。如果本文对你起到了帮助，希望可以点赞