数据结构与算法完整版 | 超详细图解，看这一篇就够了

红太狼 2024-03-31 12:17 23阅读 0赞

### 反转链表 ###

反转一个单链表。

输入: 1->2->3->4->5 输出: 5->4->3->2->1

###  ###

解法1：

迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每次处理都会改变状态、直至到达最终状态

从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next

![aec0ef55c34be7ff30f62f7d68626936.jpeg][]

1、将下一个节点指针保存到next变量 next = curr.next

2、将下一个节点的指针指向prev，curr.next = prev

3、准备处理下一个节点，将curr赋值给prev

4、将下一个节点赋值为curr，处理一个节点

###  ###

解法2：

递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr将所有的小问题解决，大问题即解决

![48e7dd4c856c5e3ac4cc870c8b47409f.jpeg][]

只需每个元素都执行curr.next.next = curr，curr.next = null两个步骤即可为了保证链不断，必须从最后一个元素开始

public class ReverseList \{ static class ListNode\{ int val; ListNode next; public ListNode(int val, ListNode next) \{ this.val = val; this.next = next; \} \} public static ListNode iterate(ListNode head)\{ ListNode prev = null,curr,next; curr = head; while(curr != null)\{ next = curr.next; curr.next = prev; prev = curr; curr = next; \} return prev; \} public static ListNode recursion(ListNode head) \{ if (head == null || head.next == null) \{ return head; \} ListNode newHead = recursion(head.next); head.next.next = head; head.next = null; return newHead; \} public static void main(String\[\] args) \{ ListNode node5 = new ListNode(5,null); ListNode node4 = new ListNode(4,node5); ListNode node3 = new ListNode(3,node4); ListNode node2 = new ListNode(2,node3); ListNode node1 = new ListNode(1,node2); //ListNode node = iterate(node1); ListNode node\_1 = recursion(node1); System.out.println(node\_1); \} \}

![66ddb77f5975f52767d2b8be2817d17c.jpeg][]

案例实战，举一反三

有如下链表：

![19b1c9922eeda03630a6650e35afc5ec.jpeg][]

要求对链表进行反转，反转后的链表如下：

![003a7d8a6c7aca9b27f6b277bbe411ec.jpeg][]

题目解析

反转链表，就是将链表中每一个节点的 next 引用指向其前驱节点。链表默认自带一个引用，这个引用指向了头节点，记为 n1。首先尝试将 n1 的 next 引用进行反转：

![a84046f68405ca1552f5526152403934.jpeg][]

可以发现，① 的 next 引用指向了空，由于 ① 切断了指向 ② 的引用，导致 n1 无法移动到 ② 和 ③，此时可以再引入一个引用，记为 n2，n2 指向 ②：

![d1256c989acec3ffbb56a03690de7458.jpeg][]

对 ② 进行反转：

![6811095b3d49ef332a6611c5e2157128.jpeg][]

这时候 ③ 丢失了，是否可以复用现有的引用来访问到 ③ 呢，答案是不行的。 ② 的前驱节点需要通过 n1 来访问，此时需再引入一个新的引用 n3，来指向 ③：

![544d01f94a0fc6bc1a8cbde2444a6817.jpeg][]

对 ③ 进行反转：

![214a98cace7c1bdd0d94fef17bf10af9.jpeg][]

这时候三节点链表就完成了反转，题目到这是否就分析结束了呢？再引入一个节点 ④，如图：

![cb8b394e10cd92847ecc730edc756afb.jpeg][]

不难发现，④ 节点又丢失了。再思考，能否复用现有引用，来访问到 ④，光从上图的结果来看，是不行的，一旦一个节点完成了反转，其后继节点就丢失了，除非创建与链表节点数量一致的引用，每一个引用指向其中一个节点，然后按上述方式对每个节点完成反转。这种方式显然不够优雅，那能否在反转下一个节点之前，先将引用后移，再反转呢？

接下来我们尝试边反转，边移动引用。通过上述分析，反转链表至少要 3 个引用，可以得出移动的时机是在反转 ③ 的时候，我们在反转 ③ 之前，先后移引用，保证不丢失 ④：

![3f508e825d973222da8af9ff60b86c0d.jpeg][]

然后反转 ③：

![d59728fddc64891683c143609c453ad9.jpeg][]

我们需要指定一个引用，专门用来反转节点 next 指向。显然指定中间引用 n2 是合适的，n1 指向着 n2 的前驱节点，n3 指向着 n2 的后继节点，这样可以既完成反转，又不会丢失后续的节点。因此，我们在反转 ③ 之后，继续后移引用，使得 n2 指向 ④，完成对 ④ 的反转：

![3255d8266a9af15192e33594f6871de4.png][]

这里将移动和反转做了合并，可以看到，现在整个链表已经完成了反转。

###  ###

代码实现

现在，我们只需将上述的分析结果翻译成代码即可。经过分析可知，反转链表一共需要三个引用，为了清晰直观，依次记为 prev、node、next，node 用于反转节点 next 指针。每当完成一次反转，三个引用便整体向后移动一个节点。代码实现如下：

public static Node reverse(Node node) \{ if (node == null || node.next == null) \{ return node; \} Node prev = null; Node next = node.next; //next 指向空时，只需再进行最后一次反转 while (next != null) \{ //反转节点 node.next = prev; //引用后移 prev = node; node = next; next = next.next; \} //反转最后一个节点 node.next = prev; //返回反转后的链表头引用 return node; \}

需要注意的是，当 next 引用指向空时，末尾最后一个节点还未反转，所以在循环外要再反转一次。

另外，这里必须将处理好的 node 引用在方法中返回出去，通过拿方法的返回值来获取反转后的链表。如果仍然使用传入的 node，会发现 node 只剩下一个节点。有如下测试代码：

//定义链表：1 -> 2 -> 3 Node node = new Node(1); node.next = new Node(2); node.next.next = new Node(3); System.out.println("原始链表："); show(node); //反转链表 Node rNode = reverse(node); System.out.println("反转后："); show(node); show(rNode);

结果如下：

原始链表： \[Node\{num=1, next=2\}, Node\{num=2, next=3\}, Node\{num=3, next=\}\] 反转后： \[Node\{num=1, next=\}\] \[Node\{num=3, next=2\}, Node\{num=2, next=1\}, Node\{num=1, next=\}\]

这是因为在 Java 中传递的是值，而不是引用。反转后的图例如下：

![0a81bf3f7029af6434b14585d4d43915.jpeg][]

在传递 node 时，是将 node 保存的内存地址复制了一份，传给了方法参数 node，方法中对 node 的移动，不会影响方法外的 node。

反转链表至此完成，在解决链表相关问题时，要时刻注意不能丢失节点，在修改节点 next 或者 prev 指针时，都要保证仍能访问到其他节点，如果发现无法复用现有引用，可以尝试新增引用。保证了这一点之后，剩下的就是按题目要求实现即可。

篇幅有限，其他内容就不在这里一一给大家解析了，整理不易，非常欢迎大家一起学习交流，喜欢文章记得关注我点赞哟，感谢支持！

> 该资料获取方式：关注+转发后，**私信我** 获取完整版算法合集！

![41196dbcd2ae37f549030d986f2d8f00.png][]

![b3f964791ba05fdcae151d328d7bce4f.png][]

[aec0ef55c34be7ff30f62f7d68626936.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4e41384c05ce49298f0dcbbfbfff3fcb.jpeg
[48e7dd4c856c5e3ac4cc870c8b47409f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9140eb3e51904b78b36b07f682c44086.jpeg
[66ddb77f5975f52767d2b8be2817d17c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0dce9dc3f546433b9fe53ca50a3ed6cb.jpeg
[19b1c9922eeda03630a6650e35afc5ec.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6199ff160f7c4b31ba3d0c5a2efd832d.jpeg
[003a7d8a6c7aca9b27f6b277bbe411ec.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1917d93ae8ec4a53b83474cadc3ccdfc.jpeg
[a84046f68405ca1552f5526152403934.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fed14bb1e6484457b419c8acf80c1b5b.jpeg
[d1256c989acec3ffbb56a03690de7458.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7076bbaaa3bd442281265ffc836eacce.jpeg
[6811095b3d49ef332a6611c5e2157128.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/22c2515c846845f8a0a91be39cbffa8c.jpeg
[544d01f94a0fc6bc1a8cbde2444a6817.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e22f8f246a2a4af5bcbcf0b9746a90f6.jpeg
[214a98cace7c1bdd0d94fef17bf10af9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a711f266ec4a45bfa9d9db67b3e52084.jpeg
[cb8b394e10cd92847ecc730edc756afb.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bc03305dd1bf43e48d70d437958e2d29.jpeg
[3f508e825d973222da8af9ff60b86c0d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f74f4d3325f5405cb91e34f673863890.jpeg
[d59728fddc64891683c143609c453ad9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fe02f004dfb846e0beeef10412392619.jpeg
[3255d8266a9af15192e33594f6871de4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f2a9b80579424d7cab7c1709373166a2.png
[0a81bf3f7029af6434b14585d4d43915.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e5947a71ba6340b1a9ec27dd4ab1e080.jpeg
[41196dbcd2ae37f549030d986f2d8f00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7aeee713c8e04817aa0508c2eb6e9796.png
[b3f964791ba05fdcae151d328d7bce4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/63218fa9588349ec8af0128f16a7a2b0.png