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

这篇具有很好参考价值的文章主要介绍了Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java 

 文章来源地址https://www.toymoban.com/news/detail-752592.html

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

 

文章目录

        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++;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;

            @Override
            public boolean hasNext() {

                return p != null;
            }

            @Override
            public 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 结束循环。

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

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

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

        这就是头插节点的流程。

代码如下:

    //方法二: 改变旧节点的指向
    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,这里就拿到了新链表的头节点了。接下来要考虑的是,如何将剩下的节点反转呢?

 先来看看递归的流程图:

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

     

分析如下:  

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

几个简单的过程:

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

代码如下:

    //方法四:双引用
    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++;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;

            @Override
            public boolean hasNext() {

                return p != null;
            }

            @Override
            public 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;
    }

}

Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现),Java 数据结构与算法篇,算法,java

 

到了这里,关于Java 算法篇-深入了解单链表的反转(实现:用 5 种方式来具体实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 从前序与中序遍历序列来构造二叉树         1.1 实现从前序与中序遍历序列来构造二叉树思路            1.2 代码实现从前序与中序遍历序列来构造二叉树         2.0 从中序

    2024年02月05日
    浏览(77)
  • Java LeetCode篇-深入了解二叉树经典解法(三种方式实现:获取二叉树的最大深度)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 对称二叉树         1.1 判断对称二叉树实现思路         1.2 代码实现:判断对称二叉树         2.0 二叉树的最大深度         2.1 使用递归实现获取二叉树的最大深度思

    2024年02月05日
    浏览(77)
  • 【一起学数据结构与算法】快速教你了解并实现单链表

    此篇是对单链表知识的学习和实现,基本上大体的方法实现和思路都已经表达,如果有不对的地方,还请各位大佬多多指教! 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素

    2024年02月19日
    浏览(44)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(58)
  • 单链表反转(逆置)——(四种方法实现)

    链表逆置就是把最后一个数据提到最前面,倒数第二个放到第二个……依次类推,直到第一个到最后一个。 由于链表没有下标,所以不能借助下标来实行数据的逆置,要靠空间的转移来完成链表的逆置,这里采用没有头节点的链表来实现逆置。 第一种——头插法 算法思想:

    2024年02月11日
    浏览(33)
  • 速学数据结构 | 手把手教你会单链表的构建方式

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 : 《初阶数据结构》《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊!今天给大家带来的是初阶数据结构中单链表的构建方式,手把手教会你单链表 !    ⛳️ 链表是指一种逻辑上是连在一

    2024年02月08日
    浏览(93)
  • 【数据结构与算法】单链表的排序算法(选择,冒泡,递归)

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似,但是链表需要先找到里面最小或者最大的值,然后将这个值用改链语句进行操作 我们先看这个改链语句的操作(min是笔者打错了应该是max,但是图已经画好了就没有改)

    2024年02月04日
    浏览(56)
  • 【数据结构与算法】单链表的插入和删除

    🔥 本文由 程序喵正在路上 原创,CSDN首发! 💖 系列专栏: 数据结构与算法 🌠 首发时间:2022年9月21日 🦋 欢迎关注🖱点赞👍收藏🌟留言🐾 🌟 一以贯之的努力 不得懈怠的人生 众所周知,顺序表中的每个结点中只存放数据元素,其优缺点为: 优点:可随机存取,存储

    2024年02月07日
    浏览(43)
  • 【数据结构与算法】单链表的增删查改(附源码)

      这么可爱的猫猫不值得点个赞吗 😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构  2.物理结构 三.结构体的定义 四.增加 1.尾插   SListpushback 2.头插  SListpushfront 五.删除 1.尾删  SListpopback 2.头删  SListpopfront 六.查找  插入  释放   打印 1.查找

    2024年02月02日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包