题目描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1： 示例 2： 示例 3：

提示：

  • 链表中节点的数目范围是 [0, 5000]

  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路及解答

双指针解法（迭代解法）

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示: 之前链表的头节点是元素1， 反转之后头结点就是元素5，这里并没有添加或者删除节点，仅仅是改变next指针的方向。

双指针反转：

  1. 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

  2. 开始反转：把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre，此时已经反转了第一个节点了。

  3. 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

  4. 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时return pre指针就可以了，pre指针就指向了新的头结点。

上面操作单链表的代码逻辑不复杂，而且也不止这一种正确的写法。但是操作指针的时候，有一些很基本、很简单的小技巧，可以让你写代码的思路更清晰：

需要注意循环的终止条件。要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。

递归解法

上面的迭代解法操作指针虽然有些繁琐，但是思路还是比较清晰的。如果现在让你用递归来反转单链表，有没啥想法？对于刚开始刷题的小伙伴来说，可能很难想到，这很正常。如果有解过二叉树系列算法题，回头再来看这道题，就有可能有想法解这道题了。因为二叉树结构本身就是单链表的延伸，相当于是二叉链表嘛，所以二叉树上的递归思维，套用到单链表上是一样的。

递归反转单链表的关键在于，这个问题本身是存在子问题结构的。

例如，现在给你输入一个以 1 为头结点单链表 1->2->3->4，那么如果忽略这个头结点 1，只拿出 2->3->4 这个子链表，它也是个单链表对吧？

那么这个 reverseList 函数，只要输入一个单链表，就能给我反转对吧？那么能不能用这个函数先来反转 2->3->4 这个子链表呢，然后再想办法把 1 接到反转后的 4->3->2 的最后面，是不是就完成了整个链表的反转？

也就是

这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。

对于「分解问题」思路的递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverseList 函数定义是这样的：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

明白了函数的定义，再来看这个问题，这段代码似乎就很好理解了

为什么是 head.next.next = head;？这行代码是整个递归算法的核心，它的作用是在“回溯”阶段，将当前节点（head）的下一个节点的指针反转过来，让它指向当前节点（head）。

我们可以通过一个例子来理解这个过程。假设有一个链表 1 -> 2 -> 3 -> null。

递归深入：函数会不断调用自身，直到链表末尾。

  • reverseList(1) 调用 reverseList(2)

  • reverseList(2) 调用 reverseList(3)

  • reverseList(3) 发现 3.next 为 null，触发终止条件，返回 3。此时 last 就是 3，它在整个回溯过程中保持不变，成为新链表的头结点。

回溯与反转：从最深层开始返回，并执行 head.next.next = head;。

  • 回到 reverseList(2)：此时 head 是节点 2。在调用 reverseList(3) 之前，head.next 指向的是节点 3。所以 head.next.next = head 等价于 3.next = 2。这样，2 和 3 之间的指向就反过来了，变成了 3 -> 2。

  • 回到 reverseList(1)：此时 head 是节点 1。同理，head.next 仍然指向节点 2。所以 head.next.next = head 等价于 2.next = 1。这样，1 和 2 之间的指向也反过来了。

最终，通过这两步操作，链表就从 1 -> 2 -> 3 变成了 3 -> 2 -> 1。

可以用 last.next = head 吗？不可以，这样做是错误的。

  • last 的角色：变量 last 始终指向已经反转好的那部分子链表的头结点。在我们的例子中，它就是原链表的最后一个节点 3。在整个递归返回的过程中，last 的值是不变的。

  • 错误的后果：如果你写 last.next = head，意味着你总是试图让新链表的头结点（例如 3）直接指向当前正在处理的节点（例如 2 或 1）。这会破坏已经建立好的连接，无法形成正确的链式结构，甚至可能导致循环引用。

借用栈

借用栈先进后出的能力（或者双端队列，一端进，另一端出也是一样的效果）

  • 首先将所有的结点入栈

  • 然后创建一个虚拟虚拟头结点，让cur指向虚拟头结点。然后开始循环出栈，每出来一个元素，就把它加入到以虚拟头结点为头结点的链表当中，最后返回即可。

解法总结

最好的方式还是双指针解法；如果数据量较大，递归解法和借用栈的方式都有可能导致栈溢出的情况