题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
这道题是链表题里最经典的一道基础题。 虽然代码不长，但非常适合用来练习链表指针的移动和修改。
示例分析
示例 1
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
原链表：
1 -> 2 -> 3 -> 4 -> 5 -> null
反转之后：
5 -> 4 -> 3 -> 2 -> 1 -> null
示例 2
输入: head = [1,2]
输出: [2,1]
示例 3
输入: head = []
输出: []
如果链表为空，直接返回空链表即可。
解题思路
这道题最常见的做法就是迭代反转链表。
我们在遍历链表的过程中，把每一个节点的 next 指针方向反过来。
比如原来是：
1 -> 2 -> 3
我们要一步一步变成：
1 <- 2 <- 3
最后返回新的头节点。
你给出的代码如下：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
这份代码非常标准，也是面试中最推荐掌握的写法。
核心思路
反转链表时，最重要的一点是：
在修改当前节点的
next指针之前，一定要先保存原来的下一个节点。
因为一旦执行：
cur.next = pre;
当前节点原本指向后面的链就断掉了。
所以必须提前用一个临时变量保存：
ListNode tmp = cur.next;
这样后面才能继续往后遍历。
三个指针分别表示什么
这道题核心就是三个指针：
-
pre：表示当前节点反转后应该指向的前一个节点 -
cur：表示当前正在处理的节点 -
tmp：表示当前节点原本的下一个节点，用来防止链表断掉
初始状态：
-
pre = null -
cur = head
为什么 pre 一开始是 null？
因为反转之后，原链表的头节点会变成新链表的尾节点，而尾节点的 next 应该指向 null。
代码解析
1. 初始化两个指针
ListNode cur = head, pre = null;
-
cur指向当前节点，初始为原链表头节点 -
pre指向当前节点前面的节点，初始为空
2. 遍历链表
while(cur != null) {
只要当前节点不为空，就继续处理。
3. 先保存当前节点的下一个节点
ListNode tmp = cur.next;
这是整道题最关键的一步。
如果不先保存 cur.next，后面一旦修改了指针方向，就找不到后续节点了。
4. 反转当前节点的指针方向
cur.next = pre;
这一句就是“反转”的真正操作。
让当前节点的 next 从原来的“指向后面”，改成“指向前面”。
5. pre 向前移动
pre = cur;
当前节点已经处理完了，所以它就变成了下一轮的“前一个节点”。
6. cur 继续向后移动
cur = tmp;
通过之前保存的 tmp，继续处理原链表中的下一个节点。
7. 返回结果
return pre;
循环结束时，cur == null，说明整个链表都处理完了。 此时 pre 指向的就是反转后的新头节点。
完整执行过程模拟
我们以这个链表为例：
1 -> 2 -> 3 -> null
初始状态：
pre = null
cur = 1
第一次循环
先保存下一个节点：
tmp = 2
反转指针：
1 -> null
然后移动指针：
pre = 1
cur = 2
此时链表可以理解为：
已反转部分: 1 -> null
未处理部分: 2 -> 3 -> null
第二次循环
先保存下一个节点：
tmp = 3
反转指针：
2 -> 1 -> null
然后移动指针：
pre = 2
cur = 3
此时：
已反转部分: 2 -> 1 -> null
未处理部分: 3 -> null
第三次循环
先保存下一个节点：
tmp = null
反转指针：
3 -> 2 -> 1 -> null
然后移动指针：
pre = 3
cur = null
循环结束，返回 pre。
最终结果：
3 -> 2 -> 1 -> null
为什么不会丢失链表
很多同学第一次做这题时，最容易担心的是：
cur.next = pre之后，链表不是断了吗？
确实会断。
但关键就在于，我们在断开之前已经用 tmp 把后面的链保存下来了：
ListNode tmp = cur.next;
所以虽然当前节点的 next 改了方向，但我们仍然可以通过 tmp 找到原来的后续节点。
这就是这道题最核心的技巧。
递归写法简介
这道题除了迭代写法，还可以用递归来做。
递归写法的核心思想是：
-
先递归反转后面的链表
-
再让当前节点接到后面
不过递归写法理解成本稍高，而且会额外使用递归栈空间。 所以在面试中，通常更推荐你掌握这种迭代写法。
复杂度分析
时间复杂度
O(n)
只遍历了一次链表。
空间复杂度
O(1)
只使用了常数个指针变量，没有额外开辟空间。
总结
这道题虽然基础，但非常经典，核心就三步：
-
先保存当前节点的下一个节点
-
再把当前节点的
next指向前一个节点 -
最后整体向前推进
也就是这三句最关键：
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
只要把这几步的顺序记住，这道题就非常稳。
你可以把这题总结成一句话：
一边遍历链表，一边把指针方向反过来。
