本文为原创文章，如需转载请注明出处，谢谢!
扯淡
今天出去面试又碰到这题了，从毕业到现在面试这么多次，也碰上了不少次这道题，可见这题的重要性。然而面试前没复习这题，导致面试的时候底气不足，虽然思路说对了，但是还是对自己的表现不满意。原因就是算法题当时解出来的时候印象非常深刻，但是过后的工作中很少涉及，很容易淡忘。所以必须要总结，把每次面试的坑都总结下来，为之后的面试做准备。
正题
废话不说了，直接给大家看张我总结的思路图。
我们对照着图一步一步的分析，帮助大家记忆。
1.定义三个节点引用
我们用 java 语言实现就需要先定义三个节点引用，Prev表示上一个节点，Head表示当前节点，Next则表示下一个节点。然后让 Prev 指向 Null，Head 指向链表的头节点，Next 也指向 Null。
2.逆序过程
最重要的一步，这步会了，以后的步骤都是重复第一步，循环即可。
(1) 初始状态，Head—>A，Prev—>Null，Next—>Null。
(2) Next = Head.next，首先用 Next 引用缓存下一个节点，为什么这是第一步？因为如果先将 Head.next 逆序指向前面节点，下一个节点就丢了，就没有引用可以拿到下一个节点了。
(3) Head.next = Prev，再将当前节点的下一个节点指向 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) Head.next = Prev，将当前节点的链和前一节点连接，现在 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) Head.next = Prev，将当前节点的链和前一节点连接，现在 C.next—>Prev(B)
(4) 目前情况是，Prev—>B，Head—>C（头结点），Next—>D，B.next—>Prev(B)，同样地，向右移动 Prev 和 Head，即 Prev->Head(C)，Head—>Next(D)。
5.伪代码
分析了这么多，我们知道了逆序的流程，得到如下伪代码:
Next = Head.next;
Head.next = Prev;//让链指向前节点
Prev = Head;//右移
Head = Next;
6.结束条件
循环终止的条件是什么呢？请看图中后两条，当只剩一个节点 E 没完成逆序的时候，还需要再重复一次刚才的步骤，向右移动 Prev 和 Head 后就得到了最后一条，看到 Head 指向了 Null（是右移 Head 的时候，Head—> Next，此时的 Next 为 E.next=Null）。所以判断条件为 while(Head != null)。
7.完整代码
最后，附上完整代码。空间复杂度为 O(n)。
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null) return null;
ListNode prev = null;
ListNode next = null;
while(head != null) {
next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
这次详细总结了以后，相信再面试再也不怕「单链表逆序」了！
我也是个初学者，如写的有问题，请及时联系我！感谢！
