链表反转的C语⾔实现（迭代法和递归法）——图⽂详解实现功能：
原链表：head->0->1->2->3->4->NULL
反转后：head->4->3->2->1->0->NULL
1.迭代法
1.得到链表后，先定义两个指针。current指向头结点；prev指向NULL。
2.执⾏操作：
定义临时指针next储存当前节点指向的下⼀个节点的地址。
struct node* next = current->next;
把prev的值赋给当前节点的下⼀个地址值(头节点指向NULL，其他节点指向上⼀个节点)。
current->next = prev;
把当前节点地址给prev。
prev = current;
next值赋给current，current指针向后⼀个节点移动。
current = next;
3.不断重复上⼀步的操作，当前节点指向上⼀个节点后current指针和prev指针继续后移，不断迭代。
4.直到current指针移到NULL时prev指向最后⼀个节点，此时链表反转完成，将prev返回为链表头head。
代码：
struct node*reverse1(struct node* head)
{
struct node* prev =NULL;
struct node* current = head;
while(current){
struct node* next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
2.递归法
传⼊头结点的值后不断调⽤⾃⼰，下⼀个函数压栈，传⼊的值依次为下⼀个节点的地址。当压顶的函数参数指向NULL时递归结束，函数逐次释放，执⾏后⾯的代码：
此时最顶的函数已经释放，返回的指针即为链表头，声明head保存，下⾯每个函数的指针指向节点都把下⼀个节点的next指向⾃⼰并将当前的next指向空，实现链表反转，直到第⼀个函数结束返回head。
代码：
struct node*reverse2(struct node* p)
{
if(p->next ==NULL){//递归结束
return p;
}
struct node* head =reverse2(p->next);//保存链表头的值 p->next->next = p;
p->next =NULL;
return head;
}
运⾏程序：
运⽤以上的两种⽅法实现链表两次反转
#include <stdio.h>
#include <stdlib.h>
/*定义结构体*/
struct node
{
int data;
struct node *next;
};
/*头插法创建链表*/
struct node*insert(struct node *head,int data)
{
struct node *new = head;
new =(struct node *)malloc(sizeof(struct node));
new->data = data;
if(head ==NULL){
head = new;
}else{
new->next = head;
head = new;
}
return head;
}
/*遍历链表*/
void printLink(struct node *head)
{
printf("head->");
while(head !=NULL){
printf("%d->",head->data);
head = head->next;
}
printf("NULL");
putchar('\n');
}
/*迭代法反转*/
struct node*reverse1(struct node* head)
{
struct node* prev =NULL;
struct node* current = head;
while(current){
struct node* next = current->next;
current->next = prev;
prev = current;
prev = current;
current = next;
}
return prev;
}
/*递归法反转*/
struct node*reverse2(struct node* p) {
if(p->next ==NULL){
return p;
}
struct node* head =reverse2(p->next); p->next->next = p;
p->next =NULL;
return head;
}
int main()
{
int n=5;
struct node *head =NULL;
printf("Link:\n");//随便创建⼀个链表while(n--){
head =insert(head,n);
}
printLink(head);
printf("reverse1:\n");//迭代法反转
head =reverse1(head);
printLink(head);
printf("reverse2:\n");//递归法反转
head =reverse2(head);
printLink(head);
c语言编写递归函数
return0;
}
运⾏结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。