个人中心
gpt4 book ai didi

如何使用递归和非递归方式反转单向链表

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章如何使用递归和非递归方式反转单向链表由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

问题： 给一个单向链表，把它从头到尾反转过来。比如： 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.

最后此篇关于如何使用递归和非递归方式反转单向链表的文章就讲到这里了,如果你想了解更多关于如何使用递归和非递归方式反转单向链表的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： 山海镜花宵明灵器怎么选 宵明灵器搭配推荐
文章推荐： MySQL修改innodb_data_file_path参数的一些注意事项
文章推荐： Mysql查询很慢卡在sending data的原因及解决思路讲解
文章推荐： 山海镜花宵明和天狐哪个好用 宵明天狐对比分析
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com