使用递归和非递归实现单链反转详解
本篇文章讲述了使用递归以及非递归如何实现单链反转,可能有很多同学并不太了解单链反转是什么,那么就让我们废话少说,直接看本篇文章吧!
在题目中给出了可使用递归与迭代两种算法的提示。
因为对递归理解不深刻,首先采用迭代编写算法,在题目中的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中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

热门话题

C++函数的递归深度受到限制,超过该限制会导致栈溢出错误。限制值因系统和编译器而异,通常在1000到10000之间。解决方法包括:1.尾递归优化;2.尾调用;3.迭代实现。

是的,C++Lambda表达式可以通过使用std::function支持递归:使用std::function捕获Lambda表达式的引用。通过捕获的引用,Lambda表达式可以递归调用自身。

华为手机如何实现双微信登录?随着社交媒体的兴起,微信已经成为人们日常生活中不可或缺的沟通工具之一。然而,许多人可能会遇到一个问题:在同一部手机上同时登录多个微信账号。对于华为手机用户来说,实现双微信登录并不困难,本文将介绍华为手机如何实现双微信登录的方法。首先,华为手机自带的EMUI系统提供了一个很便利的功能——应用双开。通过应用双开功能,用户可以在手机上同

编程语言PHP是一种用于Web开发的强大工具,能够支持多种不同的编程逻辑和算法。其中,实现斐波那契数列是一个常见且经典的编程问题。在这篇文章中,将介绍如何使用PHP编程语言来实现斐波那契数列的方法,并附上具体的代码示例。斐波那契数列是一个数学上的序列,其定义如下:数列的第一个和第二个元素为1,从第三个元素开始,每个元素的值等于前两个元素的和。数列的前几个元

递归算法通过函数自调用解决结构化的问题,优点是简洁易懂,缺点是效率较低且可能发生堆栈溢出;非递归算法通过显式管理堆栈数据结构避免递归,优点是效率更高且避免堆栈溢出,缺点是代码可能更复杂。选择递归或非递归取决于问题和实现的具体限制。

如何在华为手机上实现微信分身功能随着社交软件的普及和人们对隐私安全的日益重视,微信分身功能逐渐成为人们关注的焦点。微信分身功能可以帮助用户在同一台手机上同时登录多个微信账号,方便管理和使用。在华为手机上实现微信分身功能并不困难,只需要按照以下步骤操作即可。第一步:确保手机系统版本和微信版本符合要求首先,确保你的华为手机系统版本已更新到最新版本,以及微信App

递归函数是一种在字符串处理中反复调用自身来解决问题的技术。它需要一个终止条件以防止无限递归。递归在字符串反转和回文检查等操作中被广泛使用。

在当今的软件开发领域中,Golang(Go语言)作为一种高效、简洁、并发性强的编程语言,越来越受到开发者的青睐。其丰富的标准库和高效的并发特性使它成为游戏开发领域的一个备受关注的选择。本文将探讨如何利用Golang来实现游戏开发,并通过具体的代码示例来展示其强大的可能性。1.Golang在游戏开发中的优势作为一种静态类型语言,Golang在构建大型游戏系统
