首页 后端开发 php教程 使用递归和非递归实现单链反转详解

使用递归和非递归实现单链反转详解

Mar 14, 2018 pm 12:48 PM
反转 实现 递归

本篇文章讲述了使用递归以及非递归如何实现单链反转,可能有很多同学并不太了解单链反转是什么,那么就让我们废话少说,直接看本篇文章吧!
在题目中给出了可使用递归与迭代两种算法的提示。
因为对递归理解不深刻,首先采用迭代编写算法,在题目中的head结点认为是含有数据的第一个结点
题目思路:从头结点出发,向后遍历,按照顺序一个个逐渐实现结点之间链的反转。
首先尝试使用2个指针完成操作,失败

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head -> next)
  {
 pre = head;
 head = head -> next;
 head -> next = pre; 
  }
  return head;
};
登录后复制

理由如下:在反转过程中,head ->next 已经反向,无法继续向后遍历,因此增加一个指针采用3个指针完成操作

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head)
  {
 ListNode* next = head -> next;
 head -> next = pre;//head是尾结点,指针置空
 head = next;
 pre = head; 
  }
  return pre;           //head = NULL
};
登录后复制

递归不会,参考Discuss后,理解。
思路如下:通过递归使得头结点不断向后遍历,直到终止条件:达到尾结点 后停止。
代码如下:

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
//终止条件,达到尾结点停止
if(head == NULL || head ==NULL)
return head;
else
{
//头结点向后移动
ListNode* temp = reverList(head->next);
head->next->next = head;   //1
head->next = NULL;         //2
}
return temp;
};
登录后复制

到达递归终止条件时呈现的状态如下:




返回上一层递归后状态如下:


经过注释1、2的两行代码后,状态如下


可见head结点的位置与递归层数有关,而temp作为反转后的头结点,位置始终不动,从而达到反转效果。
递归代码虽能看懂,然而我现在还并不会设计,还是个菜鸡。

相关文章:

PHP实现单链表翻转操作示例



以上是使用递归和非递归实现单链反转详解的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门文章

仓库:如何复兴队友
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热门文章

仓库:如何复兴队友
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热门文章标签

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

C++ 函数的递归实现:递归深度有限制吗? C++ 函数的递归实现:递归深度有限制吗? Apr 23, 2024 am 09:30 AM

C++ 函数的递归实现:递归深度有限制吗?

C++ lambda 表达式是否支持递归? C++ lambda 表达式是否支持递归? Apr 17, 2024 pm 09:06 PM

C++ lambda 表达式是否支持递归?

华为手机如何实现双微信登录? 华为手机如何实现双微信登录? Mar 24, 2024 am 11:27 AM

华为手机如何实现双微信登录?

如何在华为手机上实现微信分身功能 如何在华为手机上实现微信分身功能 Mar 24, 2024 pm 06:03 PM

如何在华为手机上实现微信分身功能

C++ 函数的递归实现:递归与非递归算法的比较分析? C++ 函数的递归实现:递归与非递归算法的比较分析? Apr 22, 2024 pm 03:18 PM

C++ 函数的递归实现:递归与非递归算法的比较分析?

PHP编程指南:实现斐波那契数列的方法 PHP编程指南:实现斐波那契数列的方法 Mar 20, 2024 pm 04:54 PM

PHP编程指南:实现斐波那契数列的方法

C++ 函数递归详解:递归在字符串处理中的应用 C++ 函数递归详解:递归在字符串处理中的应用 Apr 30, 2024 am 10:30 AM

C++ 函数递归详解:递归在字符串处理中的应用

掌握Golang如何实现游戏开发的可能性 掌握Golang如何实现游戏开发的可能性 Mar 16, 2024 pm 12:57 PM

掌握Golang如何实现游戏开发的可能性

See all articles