单链表反转C语言代码

Post author:xfxia
Post published:2023年9月10日
Post category:其他

单链表反转的整体代码如下：

#include<stdio.h>
#include<stdlib.h>

typedef struct LinkedNode{
    int data;
    struct LinkedNode *next;
}node; 
int main(){
	node* head = NULL;
	node* sentinelNode = (node *)malloc(sizeof(node));
	head = sentinelNode;
	printf("sentinelNode data：%d\n",sentinelNode->data);
	int i = 1;
	//recordNode用来记录一些循环中的结点
	node* recordNode = (node *)malloc(sizeof(node));
	sentinelNode->next = recordNode;
	//使用while循环把1~3这几个值放到链表里边 
	while(i<=3){
		recordNode->data = i;
		node* creatingNode = (node *)malloc(sizeof(node));
		creatingNode->next = NULL;
		recordNode->next = creatingNode;
		recordNode = creatingNode;
		i++;
	}
	node* travelNode = head;
	//从1到3正序输出
	while(travelNode->next!=NULL){
		printf("%d\n",travelNode->data);
		travelNode = travelNode->next;
	}
	//下边开始进行链表反转代码
    recordNode = sentinelNode->next;
    node* presentNode = recordNode;
	node* followingNode = recordNode->next;
    while(followingNode!=NULL && followingNode->next != NULL){
		presentNode->next = followingNode->next;
		followingNode->next = recordNode;
		recordNode = followingNode;
		followingNode = presentNode->next;
	} 
    sentinelNode->next = recordNode;//将哨兵结点后续指针指向新的链表第一个数据结点
    travelNode = head;
	//逆序输出，从3到1 
	printf("after reservering:\n");
	while(travelNode!=NULL){
		printf("data:%d\n",travelNode->data);
		travelNode = travelNode->next;
	}
	return 0; 
}

下边代码初始化一个有5个结点的链表，其中有1个哨兵结点，3个数据结点和1个尾结点（不存储数据）：

	node* recordNode = (node *)malloc(sizeof(node));
	sentinelNode->next = recordNode;
	//使用while循环把1~3这几个值放到链表里边 
	while(i<=3){
		recordNode->data = i;
		node* creatingNode = (node *)malloc(sizeof(node));
		creatingNode->next = NULL;
		recordNode->next = creatingNode;
		recordNode = creatingNode;
		i++;
	}

上边代码初始化之后，如下图所示：

在这里插入图片描述

下边介绍链表翻转的代码：

//下边开始进行链表反转代码
	recordNode = sentinelNode->next;
	node* presentNode = recordNode;
	node* followingNode = recordNode->next;

执行完这三行代码，如下图所示：

在这里插入图片描述
在图中，接下来用sN代表sentinelNode，rN代表recordNode，pN代表presentNode，fN代表followingNode。

接下来分析反转的while循环部分：

    while(followingNode!=NULL && followingNode->next != NULL){
		presentNode->next = followingNode->next;
		followingNode->next = recordNode;
		recordNode = followingNode;
		followingNode = presentNode->next;
	}

第1次执行
presentNode->next = followingNode->next;
，效果如下图：

在这里插入图片描述

第1次执行
followingNode->next = recordNode;
，如下图：

第1次执行
recordNode = followingNode;
，如下图：