C语言两种方法实现单链表反转

单链表的反转是较为常见的 *** 作，通常用迭代法和递归法来实现

• 迭代法
• 递归法

---

一.迭代法

迭代：重复执行程序中的循环指令直至达到某条件

1.初始定义变量：

首先定义两个指针，让cur指向头指针，pre指向NULL；

2.程序运行原理：

a.因为在迭代的过程中cur->next会被修改，所以先用中间变量temp储存，以便后面cur指针再往前一位；

 temp=now->next；

b.将cur->next储存后，让cur->next指向上一个数值，这样就实现了链表单个节点的反转；

	cur->next=pre;

c. 将进行迭代的两个指针全部向后移动一位，以便进行下一次迭代；

​    pre=cur;
	cur=temp;

3.迭代过程：

cur指针和pre指针不断向后移动，当循环结束时，完成整个链表的反转，此时pre指针指向最后一个数据，cur指针指向NULL,所以返回cur指针的值

    return cur;

4.完整代码：

#include 
#include 
typedef struct nodef
{
	int data;
	struct nodef *next;
} *linklist;
linklist backward_1(linklist head)
{
	linklist pre=NULL,cur=head;
	linklist temp;
	while(cur)
	{
		
		temp=now->next;
		cur->next=pre;
		pre=cur;
		cur=temp;
	}
	return pre;
}​

---

二.递归法 1.首先设置递归结束的条件；

​if(head->next==NULL)
	{
	 	return head;
	 } 

2.开始递归

不断调用自身函数并不断传入下一个节点的地址，当压顶的函数参数指向NULL时函数从栈顶开始释放，下面每个函数的指针把下一个节点的next指向自己同时让当前的next指向空，实现链表反转，直到执行第一个函数的代码返回头指针head。

​	linklist temp=backward_2(head->next);
	head->next->next=head;
	head->next=NULL; 
	return temp;

3.完整代码：

#include 
#include 
typedef struct nodef
{
	int data;
	struct nodef *next;
} *linklist;
linklist backward_2(linklist head)//递归法 
{
	if(head->next==NULL)
	{
	 	return head;//递归结束 
	 } 
	linklist temp=backward_2(head->next);
	head->next->next=head;
	head->next=NULL; 
	return temp;
}

---

完整代码实现：

#include 
#include 
typedef struct nodef
{
	int data;
	struct nodef *next;
} *linklist;
linklist nailcreate(int n,linklist head)
{
	int i;
	linklist p,end,node;
	p=head;
	for(i=0;i<n;i++)
	{
		node=(linklist)malloc(sizeof(linklist));
		//node->next=NULL;
		p->next=node;
		scanf("%d",&node->data);	
		p=node;
	}
	node->next=NULL;
	return head;
}//尾插法创建链表 
linklist backward_1(linklist head)//迭代法 
{
	linklist pre=NULL,cur=head;
	linklist temp;
	while(cur)
	{
		
		temp=cur->next;//临时储存 
		cur->next=pre;
		pre=cur;
		cur=temp;
	}
	return pre;
}
linklist backward_2(linklist head)//递归法 
{
	if(head->next==NULL)
	{
	 	return head;//递归结束 
	 } 
	linklist temp=backward_2(head->next);
	head->next->next=head;
	head->next=NULL; 
	return temp;
}
void output(linklist head)
{
	linklist p;
	p=head;
	while(p)
	{
	printf("%d ",p->data);
	p=p->next ;
	}
}//输出 
int main()
{
	linklist head;
	int n; 
	head=(linklist)malloc(sizeof(linklist));
	head->next=NULL;//链表初始化 
	printf("请输入链表长度：");
	scanf("%d",&n);//输入链表长度 
	printf("请输入链表："); 
	nailcreate(n,head);
	head=head->next;
	head=backward_1(head);//迭代法 
//	head=backward_2(head);//递归法 
	printf("反转后的链表为：");
	output(head);
	return 0;
}

---

运行结果：

---

感谢指正！