Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）
时间：2024-04-03 20:50:45 来源：网络cs 作者：往北 栏目：数据分析 阅读：
🔥博客主页： 小扳_-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++; } @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 结束循环。
对于这个链表来说，这就可以把 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++; } @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; }}
本文链接：https://www.kjpai.cn/news/2024-04-03/153583.html，文章来源：网络cs，作者：往北，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！