p11 第60题 设计一个算法，逆序单链表中的数据 电子科技大学2014年数据结构（c语言代码实现）

 通过头插法可以实现单链表的逆置

下方博客有图解：

王道p40 5.将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O（1）-CSDN博客

单链表的逆置可以通过遍历链表，逐个将节点取出并插入到新链表的头部来实现。具体步骤如下：

1.定义一个新的空链表用于存储逆置后的结果。

2.定义一个指针变量p指向原链表的头节点，定义一个指针变量q用于保存下一个要处理的节点。

3.遍历原链表，每次将指针p指向的节点取出，并将节点的next指针指向新链表的头节点，然后将新节点设置为新链表的头节点。

4.将原链表的头节点指针p指向下一个要处理的节点，继续遍历整个链表，直到p指向空节点为止。 5.返回新链表的头节点作为逆置后的结果。

本题代码如下

void nizhi(linklist* L)
{
	lnode * r = (*L)->next;
	lnode* p = r;
	(*L)->next = NULL;
	while (p)
	{
		p = r->next;
		r->next = (*L)->next;
		(*L)->next = r;
		r = p;
	}
}

完整测试代码

#include<stdio.h>
typedef struct lnode
{
	int data;
	struct lnode* next;
}lnode,*linklist;
int a[5] = { 1,2,3,4,5 };
int n = 5;
void buildlist(linklist* L)
{
	*L = (lnode*)malloc(sizeof(lnode));
	(*L)->next = NULL;
	int i = 0;
	lnode* s = *L, * r = *L;
	for (i = 0; i < n; i++)
	{
		s = (lnode*)malloc(sizeof(lnode));
		s->data = a[i];
		s->next = r->next;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}
void nizhi(linklist* L)
{
	lnode * r = (*L)->next;
	lnode* p = r;
	(*L)->next = NULL;
	while (p)
	{
		p = r->next;
		r->next = (*L)->next;
		(*L)->next = r;
		r = p;
	}
}
void print(linklist* L)
{
	lnode* k = (*L)->next;
	while (k)
	{
		printf("%d ", k->data);
		k = k->next;
	}
}
int main()
{
	linklist L;
	buildlist(&L);
	printf("原单链表为：");
	print(&L);
	nizhi(&L);
	printf("\n逆置后的单链表为：");
	print(&L);
	return 0;
}