单链表逆序知识总结 单链表的逆置的流程图

前言

今天出去面试又碰到这题了，从毕业到现在面试这么多次，也碰上了不少次这道题，可见这题的重要性。然而面试前没复习这题，导致面试的时候底气不足，虽然思路说对了，但是还是对自己的表现不满意。原因就是算法题当时解出来的时候印象非常深刻，但是过后的工作中很少涉及，很容易淡忘。所以必须要总结，把每次面试的坑都总结下来，为之后的面试做准备。

正题

废话不说了，直接给大家看张我总结的思路图。

单链表逆序

我们对照着图一步一步的分析，帮助大家记忆。

1.定义三个节点引用

我们用java
语言实现就需要先定义三个节点引用，Prev表示上一个节点，Head表示当前节点，Next则表示下一个节点。然后让 Prev 指向 Null，Head 指向链表的头节点，Next 也指向 Null。

.逆序过程

最重要的一步，这步会了，以后的步骤都是重复第一步，循环即可。

(1) 初始状态，Head—>A，Prev—>Null，Next—>Null。

(2) Next = Head.next，首先用 Next 引用缓存下一个节点，为什么这是第一步？因为如果先将 Head.next 逆序指向前面节点，下一个节点就丢了，就没有引用可以拿到下一个节点了。

(3) Prev = Head.next，再将当前节点的下一个节点指向 Head 前面的节点，完成逆序。

(4) 到现在为止，Prev—>Null，Head—>A（头结点），Next—>B，A.next—>Prev(Null)。然后，需要将 Prev 和 Head 都向右移动，即 Prev—>Head(A)，Head—>Next(B)。这步操作完之后就得到了图中的第二条。

3.再来一遍

不明白第一步没关系，我们继续分析第二步。流程和 (1) 完全一致。

(1) 初始状态，Head—>B，Prev—>A，Next—>A(上一步中没对 Next 做操作，所以还是指向 A)。

(2) Next = Head.next。同样先缓存下一个节点，现在 Next—>C。

(3) Prev = Head.next，将当前节点的链和前一节点连接，现在 B.next—>Prev(A)

(4) 目前情况是，Prev—>A，Head—>B（头结点），Next—>C，B.next—>Prev(A)，同样地，向右移动 Prev 和 Head，即 Prev->Head(B)，Head—>Next(C)。完成之后就得到了图中的第三条。

4.再来一遍，重要的事说三遍

再重复一遍，要是还不知道过程我也没辙了~

(1) 初始状态，Head—>C，Prev—>B，Next—>B。

(2) Next = Head.next。缓存下一个节点，现在 Next—>D。

(3) Prev = Head.next，将当前节点的链和前一节点连接，现在 C.next—>Prev(B)

(4) 目前情况是，Prev—>B，Head—>C（头结点），Next—>D，B.next—>Prev(B)，同样地，向右移动 Prev 和 Head，即 Prev->Head(C)，Head—>Next(D)。

5.伪代码

分析了这么多，我们知道了逆序的流程，得到如下伪代码:

6.结束条件

循环终止的条件是什么呢？请看图中后两条，当只剩一个节点 E 没完成逆序的时候，还需要再重复一次刚才的步骤，向右移动 Prev 和 Head 后就得到了最后一条，看到 Head 指向了 Null（是右移 Head 的时候，Head—> Next，此时的 Next 为 E.next=Null）。所以判断条件为while（Head ！=null）

7.完整代码

最后，附上完整代码。空间复杂度为 O(n)。

。

这次详细总结了以后，相信再面试再也不怕「单链表逆序」了！

今天在简书上看见这篇文章总结的非常不错，希望能帮助到大家。来源：简书 作者：Android_ZzT