单向链表反转java实现（单向链表反转java实现头插法）



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

文章目录

        1.0 单链表的反转说明

        2.0 单链表的创建

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

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

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

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

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

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

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

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

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

代码如下：

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

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

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

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

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

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

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

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

代码如下：

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

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

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

        这就是头插节点的流程。

代码如下：

对以上代码进行分析：

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

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

代码如下：

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

 先来看看递归的流程图：

     

分析如下：  

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

        实现思路：在原先链表中进行改变每个节点的引用，先定义出三个变量分别为 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 的节点。

几个简单的过程：

代码如下：

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

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

代码如下：

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

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/jjc/47361.html