打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
链表反转的递归和非递归实现方式

链表反转是数据结构的基本功,主要有递归和非递归两种实现方式。我们一一介绍如下:

1. 非递归实现

主要包括如下4步:

1)如果head为空,或者只有head这一个节点,return head即可;

2)从头到尾遍历链表,把reversedHead赋值给当前节点的next;

3)当前节点赋值给reversedHead;

4)遍历结束,return reversedHead。

下图试图来辅助说明:

代码如下:

node* reverseList(node* head){ if(head == NULL || head->next == NULL) return head; node* reversedHead = NULL; node* p = head; while(p != NULL) { node* q = p; q->next = reversedHead; reversedHead = q; p = p->next; } return reversedHead; }


2. 递归实现

递归的实现方式主要有4步:

1)如果head为空,或者只有head这一个节点,return head即可;

2)先遍历head->next为首的链表,得到一个头结点newHead;

3)把head赋值给head->next->next, head->next为空;

4)返回newHead。

下图也说明了上述步骤:

代码实现如下:

node* reverseList2(node* head){ if(head == NULL || head->next == NULL) return head; node* newHead = reversedList2(head->next); head->next->next = head; head->next = NULL; return newHead; }


本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
432,剑指 Offer-反转链表的3种方式
链表逆序补充
链表算法面试问题?看我就够了!
单链表的逆置
链表翻转的图文讲解(递归与迭代两种实现)
美团网 笔试 2014
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服