好资源导航 » 文章资讯 » 单链表实现反转的3种方法示例代码

单链表实现反转的3种方法示例代码

2023-08-29 04:50:04 63

前言

单链表的操作是面试中经常会遇到的问题，今天总结一下反转的几种方案：

1，两两对换

2，放入数组，倒置数组

3，递归实现

代码如下：

#include
#include
typedefstructNode
{

intdata;
structNode*pnext;


}Node,*pnode;
pnodeCreateNode()
{

pnodephead=(pnode)malloc(sizeof(Node));
if(phead==NULL)
{
printf("failtoallocatememory");
return-1;
}
phead->pnext=NULL;
intn;
pnodeph=phead;
for(inti=0;i<5;i++)
{

pnodep=(pnode)malloc(sizeof(Node));
if(p==NULL)
{
printf("failtoallocatememory");
return-1;
}
p->data=(i+2)*19;
phead->pnext=p;
p->pnext=NULL;
phead=phead->pnext;


}
returnph;
}
intlist(pnodehead)
{
intcount=0;
printf("遍历结果：\n");
while(head->pnext!=NULL)
{
printf("%d\t",head->pnext->data);
head=head->pnext;
count++;
}
printf("链表长度为：%d\n",count);
returncount;
}
pnodereverse2(pnodehead)//两两节点之间不断交换
{
if(head==NULL||head->next==NULL)
returnhead;
pnodepre=NULL;
pnodenext=NULL;
while(head!=NULL){
next=head->next;
head->next=pre;
pre=head;
head=next;
}
returnpre;
}
voidreverse1(pnodehead,intcount)//把链表的节点值放在数组中，倒置数组
{
inta[5]={0};

for(inti=0;ipnext!=NULL;i++)
{
a[i]=head->pnext->data;
head=head->pnext;

}
for(intj=0,i=count-1;jpnext=pre;
if(t==NULL)
returncur;//返回无头节点的指针，遍历的时候注意
reverse3(cur,t,t->pnext);

}

pnodenew_reverse3(pnodehead){//新的递归转置

if(head==NULL||head->next==NULL)
returnhead;
pnodenew_node=new_reverse3(head->next);
head->next->next=head;
head->next=NULL;
returnnew_node;//返回新链表头指针

}
intmain()
{
pnodep=CreateNode();
pnodep3=CreateNode();
intn=list(p);
printf("1反转之后：\n");
reverse1(p,n);
printf("\n");
printf("2反转之后：\n");
pnodep1=reverse2(p);
list(p1);
p3->pnext=reverse3(NULL,p3->pnext,p3->pnext->pnext);
printf("3反转之后：\n");
list(p3);
free(p);
free(p1);
free(p3);
return0;
}

毫无疑问，递归是解决的最简单方法，四行就能解决倒置问题。

思路参考：https://www.nhooo.com/article/156043.htm

这里注意：head->next=pre;以及pre=head->next，前者把head->next指向pre，而后者是把head->next指向的节点赋值给pre。如果原来head->next指向pnext节点，前者则是head重新指向pre，与pnext节点断开，后者把pnext值赋值给pre，head与pnext并没有断开。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对毛票票的支持。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
514930285
czq8825@qq.com

单链表实现反转的3种方法示例代码

热门推荐

随机推荐