如何使用递归和非递归方式反转单向链表
更新时间：2020年4月25日 17:45 点击：2086
问题：
给一个单向链表，把它从头到尾反转过来。比如： a -> b -> c ->d 反过来就是 d -> c -> b -> a 。
分析：
假设每一个node的结构是：
复制代码 代码如下:
class Node {
char value;
Node next;
}
因为在对链表进行反转的时候，需要更新每一个node的“next”值，但是，在更新 next 的值前，我们需要保存 next 的值，否则我们无法继续。所以，我们需要两个指针分别指向前一个节点和后一个节点，每次做完当前节点“next”值更新后，把两个节点往下移，直到到达最后节点。
代码如下：
复制代码 代码如下:
public Node reverse(Node current) {
//initialization
Node previousNode = null;
Node nextNode = null;
while (current != null) {
//save the next node
nextNode = current.next;
//update the value of "next"
current.next = previousNode;
//shift the pointers
previousNode = current;
current = nextNode;
}
return previousNode;
}
上面代码使用的是非递归方式，这个问题也可以通过递归的方式解决。代码如下：
复制代码 代码如下:
public Node reverse(Node current)
{
if (current == null || current.next == null) return current;
Node nextNode = current.next;
current.next = null;
Node reverseRest = reverse(nextNode);
nextNode.next = current;
return reverseRest;
}
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 (代码倒数第二句)。 在上面的代码中， reverseRest 的值没有改变，为该链表的最后一个node，所以，反转后，我们可以得到新链表的head。
上一篇: C++ 智能指针深入解析
下一篇: C语言小程序 杨辉三角示例代码
相关文章
- 这篇文章主要用实例讲解C#递归算法的概念以及用法，文中代码非常详细，帮助大家更好的参考和学习，感兴趣的朋友可以了解下...2020-06-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤，需要的朋友跟着参考下。...2020-04-25
- 这篇文章主要介绍了C++递归删除一个目录的实现方法,涉及到目录的操作及递归算法的应用,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题（递归法）实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#递归实现显示文件夹及所有文件并计算其大小的方法,是遍历算法中比较典型的一种应用,有不错的学习借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了使用递归实现数组求和示例，思路是给定一个含有n个元素的整型数组a，求a中所有元素的和,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C$ 笔试题之同线程Lock语句递归不会死锁，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了python 非递归解决n皇后问题的方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-16
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家，让大家理解掌握这部分内容，需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了Java中的什么场景使用递归,如何使用递归的操作，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教...2021-09-03
- 这篇文章主要介绍了在使用递归的情况下thinkphp实现无限分类，感兴趣的小伙伴们可以参考一下...2015-12-21
- 这篇文章主要介绍了使用dom4j递归解析节点内还含有多个节点的xml，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教...2021-09-25
- 这篇文章主要给大家介绍了关于如何利用Java递归解决“九连环”公式的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-21
- 这篇文章主要介绍了python递归函数求n的阶乘,优缺点及递归次数设置方式，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-10
- 这篇文章主要介绍了C#函数式编程中的递归调用详解,本文讲解了什么是尾递归、尾递归的多种方式、尾递归的代码实例等内容,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#递归实现回文判断算法,方法简单实用,需要的朋友可以参考下...2020-06-25
- 本文章来给大家介绍array_map实现递归功能,各位有需要了解的朋友可参考。 array_map(callback, arr1, arr2……);函数返回用户自定义回调函数执行后...2016-11-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家，让大家实现这样的功能，需要的朋友可以参考下...2020-04-25
- 这篇文章主要给大家介绍了关于C语言汉诺塔的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-08
- 什么是递归函数/方法？任何一个方法既可以调用其他方法也可以调用自己，而当这个方法调用自己时，我们就叫它递归函数或递归方法,接下来详细介绍需要了解的朋友可以参考下...2021-09-22