Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）

🔥博客主页： 小扳_-CSDN博客
❤感谢大家点赞👍收藏⭐评论✍  

 

 

 

文章目录

        1.0 单链表的反转说明

        2.0 单链表的创建

        3.0 实现单链表反转的五种方法

        3.1 实现单链表反转 - 循环复制（迭代法）

        3.2 实现单链表反转 - 头插法

        3.3 实现单链表反转 - 递归法

        3.4 实现单链表反转 - 三指针法

        3.5 实现单链表反转 - 第二种头插法

        4.0 实现单链表反转的五种完整代码

        1.0 单链表的反转说明

        单链表的反转是指将链表中的节点顺序逆转，即原先的链表尾部变成了头部，头部变成了尾部。比如，[1,2,3,4,5,6,7] 将这个链表的值反转得到的结果为：[7,6,5,4,3,2,1]，需要注意的是，可以用值打印出来会更好观察链表反转后的结果。

        2.0 单链表的创建

        具体的创建思路：首先要把节点进行封装成单独的类，该类中的成员包括：int value 存放值，Node next 引用下一个节点。由于该节点类为链表中的一个组成部分，因此，将该类设为静态内部类，外部类的成员为哨兵节点。

代码如下：

import java.util.Iterator;public class Linked implements Iterable<Integer>{private final Node hand;private int size;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}public Linked() {hand = new Node(0,null);}public void addLast (int value) {Node p = hand;while (p.next != null) {p = p.next;}p.next = new Node(value, null);size++;}public void addFirst(int value) {hand.next = new Node(value,hand.next);size++;}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = hand.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic Integer next() {int k = p.value;p = p.next;return k;}};}}

        为了方便对反转的五种方法进行讲解，实现了以上的头插节点、尾插节点、用迭代器循环节点的值。

本篇重点是反转的五种的方法，所以对以上的实现的 API 不太了解的话，点击以下链接去了解一下：   Java 数据结构篇-实现单链表核心API-CSDN博客

        3.0 实现单链表反转的五种方法

        迭代法：遍历链表，依次改变节点的指针方向，使其指向前一个节点。

        递归法：利用递归函数，先反转后续节点，然后再将当前节点的指针指向前一个节点。

        头插法：从头到尾遍历原链表，依次将每个节点插入到新链表的头部，形成新的反转链表。

        栈：利用栈的特性，将链表节点依次入栈，然后依次出栈构建新的反转链表。

        三指针法：使用三个指针分别指向当前节点、前一个节点和后一个节点，依次改变节点的指针方向，实现链表的反转。

        3.1 实现单链表反转 - 循环复制（迭代法）

        思路为：遍历旧的链表来取得每个节点的对应的值，然后新链表根据得到的值来创建节点进行头插节点，这样就实现了链表反转了。需要注意的是，这个方法并没有改变旧链表。

代码如下：

    //方法一: 循环复制public Linked reverseMethod1 (Linked linked) {Linked linked1 = new Linked();for (Integer integer : linked) {linked1.addFirst(integer);}return linked1;}

        分析以上代码：先创建一个新链表 linked1 然后调用头插节点的方法，通过传入旧节点的值来创建对象，也就是节点。需要注意的是，这里的增强 for 循环是已经实现了。

        3.2 实现单链表反转 - 头插法

        通过改变旧节点的节点指向来实现链表反转，当反转结束之后，旧的链表顺序就会被改变。具体思路：先要对旧节点的 hand.next 头节点从该链表独立出来，对于旧链表来说就是删除头节点，不过要记录要删除的节点，得到这个头节点之后，该节点头插到新的链表中，一直循环往复下去，直到 hand.next == null 结束循环。

        对于这个链表来说，这就可以把 remove 这个节点删除了，也为头删节点。当 hand.next = null 就说明了没有节点了，就应该结束循环了。

        这就是头插节点的流程。

代码如下：

    //方法二: 改变旧节点的指向public Linked reverseMethod2(Linked linked) {Linked linkedNew = new Linked();Node handNew = linkedNew.hand;while (hand.next != null) {//先头删Node temp = linked.hand.next;linked.hand.next = temp.next;//再头插Node tp = handNew.next;handNew.next = temp;temp.next = tp;}return linkedNew;}

对以上代码进行分析：

         先创建一个新的链表，在删除头节点前，需要将要删除的节点记录起来，如果一个对象没被引用就会被 JVM 自动回收，然后头节点指向删除节点的指向下一个的节点。头插节点前，需要将 hand.next 同样要记录，然后头节点指向新的节点，新的节点的下一个节点，正就是原先的 hand.next 。

        3.3 实现单链表反转 - 递归法

         思路：通过递归这种方式，先递出到 “底” ，得到旧链表的最后一个节点，所以递归结束的条件也就是 temp.next == null，返回该节点 temp 也就是最后的节点。递归的函数也很容易可以想出来为： 调用自己的方法名(node.next) 。

代码如下：

    //方法三: 递归public Linked reverseMethod3(Linked linked) {Linked linked1 = new Linked();linked1.hand.next = reversion(linked.hand.next);return linked1;}public Node reversion (Node node) {if (node == null || node.next == null) {return node;}Node last = reversion(node.next);node.next.next = node;node.next = null;return last;}

        对以上代码进行分析：先创建一个新的链表 linkded1 ，调用 reversion()  这个方法来得到头节点。具体来看是如何得到头节点，显而易见，就是通过递归，递到底（到尽头）取到最后一个节点，然后将这个尾节点一直返回出来，OK，这里就拿到了新链表的头节点了。接下来要考虑的是，如何将剩下的节点反转呢？

 先来看看递归的流程图：

     

分析如下：  

        假设有五个节点，在递归回归的过程中，需要做的事第五个节点指向第四个节点，第四个节点指向第三个节点...一直下去，这样是不是就实现了每个节点指向都反转了。但是需要注意的是，当第二个节点指向第一个节点，这里都没有问题，我们很容易会忽略，第一个节点原先就指向第二个节点，因此，会出现死循环，解决办法：先暂时将被指向的节点赋值为：null ，这样就完美解决了。

        3.4 实现单链表反转 - 三指针法

        实现思路：在原先链表中进行改变每个节点的引用，先定义出三个变量分别为 o1，o2，n1，一开始的时候 o1 , n1指向链表中的 hand 头节点（先来搞定没有哨兵的链表），对于 o2 指向 hand.next 。接下来就可以开始移动 o2，n1 这个两个指针了，主要的是 o1 保持不变，永远指向 hand 节点，先让 hand.next = o2.next ，这个意思就是将 hand.next 的头节点的下一个节点从链表中移出，然后将移出来的节点指向 n1 ，最后 o2 = n1 将 n1 赋值给 o2 ，o2 再接着指向 hand.next 的节点。

几个简单的过程：

代码如下：

    //方法四:双引用public Linked reverseMethod4(Linked linked) {linked.hand.next = dualPointers(linked.hand.next);return linked;}public Node dualPointers(Node hand) {Node o1 = hand;Node n1 = hand;Node o2 = o1.next;while (o2 != null) {o1.next = o2.next;o2.next = n1;n1 = o2;o2 = o1.next;}return n1;}

        通过以上的简单几个过程且结合代码来分析，应该会有一点点感觉，来总结以下，对于 o1 的动作就是站在 hand 节点中 "一动不动"， 对于 o2 可以将它看作搬运工，不断搬运 hand.next 的节点运到 n1 节点的前面（n1 的左边），具体就是先要将 o2.next 节点被 hand.next 引用，接着就是搬运了， o2.next 指向 n1 的节点，然后 n1 需要往后跳一格（往左边移动一个节点）即将 o2 赋值给 n1，然后 o2 就返回去指向 o1.next 的节点了，循环往复下去，直到当 o1.next == null 时，就该结束循环了。

        3.5 实现单链表反转 - 第二种头插法

        思路：遍历旧链表的每一个节点，然后直接插入到新链表中，这个方法个第一种头插很相似，区别就是第一种头插的方法是面向对象编程的，第二种头插的方法是面向过程来编程的。

代码如下：

    //方法五:public Linked reverseMethod5(Linked linked) {Node o1 = linked.hand.next;Linked linked1 = new Linked();Node n1 = null;while (o1 != null) {Node temp = o1.next;o1.next = n1;n1 = o1;o1 = temp;}linked1.hand.next = n1;return linked1;}

        这里也运用到了头删还有头插，跟之前的头插有所不同，这里的头插是将插入进来的节点变成为新链表的头节点，直到遍历结束为止。

        4.0 实现单链表反转的五种完整代码

import java.util.Iterator;public class Linked implements Iterable<Integer>{public Node hand;private int size;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}public Linked() {hand = new Node(0,null);}public void addLast (int value) {Node p = hand;while (p.next != null) {p = p.next;}p.next = new Node(value, null);size++;}public void addFirst(int value) {hand.next = new Node(value,hand.next);size++;}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = hand.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic Integer next() {int k = p.value;p = p.next;return k;}};}//方法一: 循环复制public Linked reverseMethod1 (Linked linked) {Linked linked1 = new Linked();for (Integer integer : linked) {linked1.addFirst(integer);}return linked1;}//方法二: 改变旧节点的指向public Linked reverseMethod2(Linked linked) {Linked linkedNew = new Linked();Node handNew = linkedNew.hand;while (hand.next != null) {//先头删Node temp = linked.hand.next;linked.hand.next = temp.next;//再头插Node tp = handNew.next;handNew.next = temp;temp.next = tp;}return linkedNew;}//方法三: 递归public Linked reverseMethod3(Linked linked) {Linked linked1 = new Linked();linked1.hand.next = reversion(linked.hand.next);return linked1;}public Node reversion (Node node) {if (node == null || node.next == null) {return node;}Node last = reversion(node.next);node.next.next = node;node.next = null;return last;}//方法四:双引用public Linked reverseMethod4(Linked linked) {linked.hand.next = dualPointers(linked.hand.next);return linked;}public Node dualPointers(Node hand) {Node o1 = hand;Node n1 = hand;Node o2 = o1.next;while (o2 != null) {o1.next = o2.next;o2.next = n1;n1 = o2;o2 = o1.next;}return n1;}//方法五:public Linked reverseMethod5(Linked linked) {Node o1 = linked.hand.next;Linked linked1 = new Linked();Node n1 = null;while (o1 != null) {Node temp = o1.next;o1.next = n1;n1 = o1;o1 = temp;}linked1.hand.next = n1;return linked1;}}

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/190739.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

OpenGL_Learn10（颜色）

OpenGL_Learn10（颜色）

1. 颜色 我们在现实生活中看到某一物体的颜色并不是这个物体真正拥有的颜色&#xff0c;而是它所反射的(Reflected)颜色。换句话说&#xff0c;那些不能被物体所吸收(Absorb)的颜色&#xff08;被拒绝的颜色&#xff09;就是我们能够感知到的物体的颜色。例如&#xff0c;太阳光…
阅读更多...
计算机提示“找不到emp.dll,无法继续执行代码”，这几种解决办法都可以解决

计算机提示“找不到emp.dll,无法继续执行代码”，这几种解决办法都可以解决

在计算机使用过程中&#xff0c;我们可能会遇到各种问题&#xff0c;其中之一就是系统文件丢失。emp.dll文件是Windows操作系统中的一个重要组件&#xff0c;如果丢失或损坏&#xff0c;可能会导致系统运行不稳定甚至无法正常启动。本文将详细介绍emp.dll文件丢失恢复的4个方法…
阅读更多...
【中间件篇-Redis缓存数据库04】Redis底层原理持久化、分布式锁

【中间件篇-Redis缓存数据库04】Redis底层原理持久化、分布式锁

Redis底层原理 持久化 Redis虽然是个内存数据库&#xff0c;但是Redis支持RDB和AOF两种持久化机制&#xff0c;将数据写往磁盘&#xff0c;可以有效地避免因进程退出造成的数据丢失问题&#xff0c;当下次重启时利用之前持久化的文件即可实现数据恢复。 RDB RDB持久化是把当…
阅读更多...
C语言--1,5,10人民币若干,现在需要18元,一共有多少种?

C语言--1,5,10人民币若干,现在需要18元,一共有多少种?

今天小编给大家分享一下穷举法的一道典型例题 一.题目描述 1,5,10人民币若干,现在需要18元,一共有多少种? 二.思路分析 总共有18块钱&#xff0c;设1元有x张&#xff0c;5元有y张&#xff0c;10元有z张&#xff0c;则有表达式&#xff1a;x5y10z18&#xff0c;穷举法最重要的…
阅读更多...
模型部署：量化中的Post-Training-Quantization（PTQ）和Quantization-Aware-Training（QAT）

模型部署：量化中的Post-Training-Quantization（PTQ）和Quantization-Aware-Training（QAT）

模型部署&#xff1a;量化中的Post-Training-Quantization&#xff08;PTQ&#xff09;和Quantization-Aware-Training&#xff08;QAT&#xff09; 前言量化Post-Training-Quantization&#xff08;PTQ&#xff09;Quantization-Aware-Training&#xff08;QAT&#xff09; 参…
阅读更多...
AIGC｜如何将Milvus集成到LangFlow中？详细代码演示！

AIGC｜如何将Milvus集成到LangFlow中？详细代码演示！

目录 一、基本介绍 二、修改langflow代码使其支持milvus 三、效果演示 langflow是一个LangChain UI&#xff0c;它提供了一种交互界面来使用LangChain&#xff0c;通过简单的拖拽即可搭建自己的实验、原型流。通过在langflow中引入Milvus&#xff0c;用户可以更方便地存储和…
阅读更多...
【Java 进阶篇】JQuery DOM操作：通用属性操作的绝妙魔法

【Java 进阶篇】JQuery DOM操作：通用属性操作的绝妙魔法

在前端的舞台上&#xff0c;JQuery犹如一位魔法师&#xff0c;为我们展现了操纵HTML元素的奇妙技巧。而在这个技巧的精妙组成中&#xff0c;通用属性操作是一门绝妙的魔法。在本篇博客中&#xff0c;我们将深入研究JQuery DOM操作中的通用属性操作&#xff0c;揭示这段魔法的神…
阅读更多...
业务出海之服务器探秘

业务出海之服务器探秘

这几年随着国内互联网市场的逐渐饱和&#xff0c;越来越多的公司加入到出海的行列&#xff0c;很多领域都取得了很不错的成就。虽然出海可以获得更加广阔的市场&#xff0c;但也需要面对很多之前在国内可能没有重视的一些问题。集中在海外服务器的选择维度上就有很大的变化。例…
阅读更多...
“第六十七天”

“第六十七天”

各位&#xff0c;昨天查找子串的方法想起来了&#xff0c;就是那个KMP算法......自己理解都有点困难&#xff0c;还看看能不能想一下&#xff0c;确实很困难啊。 不要忘了toupper函数和tolower函数不是直接改变字符的大小写&#xff0c;而是返回对应的大小写的值&#xff0c;需…
阅读更多...
2023nacos源码解读第2集——nacos-server的启动

2023nacos源码解读第2集——nacos-server的启动

nacos 是一个典型的server-client中间件&#xff0c;server这里安装最新的nacos-server 2.3.0-BETA版本 1.docker启动nacos-server 镜像详情参考nacos-docker项目的readme &#xff0c;很方便&#xff0c;但是官方提供的nacos-server镜像往往可能滞后&#xff0c;且不便于后续…
阅读更多...
Libhybris之线程局部存储TLS实例(五)

Libhybris之线程局部存储TLS实例(五)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…
阅读更多...
【STM32 CAN】STM32G47x 单片机FDCAN作为普通CAN外设使用教程

【STM32 CAN】STM32G47x 单片机FDCAN作为普通CAN外设使用教程

STM32G47x 单片机FDCAN作为普通CAN外设使用教程 控制器局域网总线&#xff08;CAN&#xff0c;Controller Area Network&#xff09;是一种用于实时应用的串行通讯协议总线&#xff0c;它可以使用双绞线来传输信号&#xff0c;是世界上应用最广泛的现场总线之一。CAN协议用于汽…
阅读更多...
Apache Druid连接回收引发的血案

Apache Druid连接回收引发的血案

问题 线上执行大批量定时任务&#xff0c;发现SQL执行失败的报错&#xff1a; CommunicationsException, druid version 1.1.10, jdbcUrl : jdbc:mysql://xxx?useUnicodetrue&characterEncodingUTF-8&zeroDateTimeBehaviorconvertToNull,testWhileIdle true, idle …
阅读更多...
Java事务详解

Java事务详解

一、事务的理解&#xff1a; 1、事务的特性&#xff1a; 1) 原子性&#xff08;atomicity&#xff09;&#xff1a;事务是数据库的逻辑工作单位&#xff0c;而且是必须是原子工作单位&#xff0c;对于其数据修改&#xff0c;要么全部执行&#xff0c;要么全部不执行。 2) 一致性…
阅读更多...
Vatee万腾外汇数字化策略：Vatee科技决策力的未来引领

Vatee万腾外汇数字化策略：Vatee科技决策力的未来引领

在外汇市场&#xff0c;Vatee万腾通过其前瞻性的外汇数字化策略&#xff0c;正引领着科技决策的未来。这一数字化策略的崭新愿景为投资者提供了更智慧、更高效的外汇投资体验&#xff0c;成为科技决策领域的翘楚。 Vatee万腾的外汇数字化策略是科技决策力未来引领的典范。通过运…
阅读更多...
消息队列之初识Rabbit及安装

消息队列之初识Rabbit及安装

文章目录 一、MQ的相关概念1.什么是MQ&#xff1f;2.为什么要用MQ2.1流量消峰2.2应用解耦2.3异步处理 3.MQ 的分类3.1.ActiveMQ3.2.Kafka3.3.RocketMQ3.4.RabbitMQ 4.MQ 的选择4.1.Kafka4.2.RocketMQ4.3.RabbitMQ 二、RabbitMQ的相关概念1.四大核心概念2.RabbitMQ 核心部分3.Ra…
阅读更多...
游戏AI：游戏开发和运营的新增长点

游戏AI：游戏开发和运营的新增长点

游戏AI&#xff08;Game AI&#xff09;是指在游戏开发运营的过程中模拟人类玩家或创建虚构性对手行为的人工智能技术。游戏AI的目标是增强游戏的互动性、可玩性和挑战性&#xff0c;使游戏中的角色能够智能地做出决策和行为。在游戏的开发和运营过程中使用人工智能技术&#x…
阅读更多...
caffe搭建squeezenet网络的整套工程

caffe搭建squeezenet网络的整套工程

之前用pytorch构建了squeezenet&#xff0c;个人觉得pytorch是最好用的&#xff0c;但是有的工程就是需要caffe结构的&#xff0c;所以本篇也用caffe构建一个squeezenet网络。 数据处理 首先要对数据进行处理&#xff0c;跟pytorch不同&#xff0c;pytorch读取数据只需要给数据…
阅读更多...
【C++】类和对象(2)--构造函数

【C++】类和对象(2)--构造函数

目录 一 概念 二 构造函数特性 三 默认构造函数 一 概念 对于以下Date类&#xff1a; class Date { public:void Init(int year, int month, int day){_year year;_month month;_day day;}void Print(){cout << _year << "-" << _month <…
阅读更多...
Qt贝塞尔曲线

Qt贝塞尔曲线

目录 引言核心代码基本表达绘制曲线使用QEasingCurve 完整代码 引言 贝塞尔曲线客户端开发中常见的过渡效果&#xff0c;如界面的淡入淡出、数值变化、颜色变化等等。为了能够更深的了解地理解贝塞尔曲线&#xff0c;本文通过Demo将贝塞尔曲线绘制出来&#xff0c;如下所示&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023