本文介绍了三种反转链表的方法：双指针、递归和栈。通过详细代码实现与分析，帮助你高效掌握反转链表技巧。无论是迭代解法还是递归反转，本文为你提供完整的思路和实现，适用于不同场景下的链表反转需求。阅读本篇文章，提升你对链表操作的理解与技能！
题目描述
给你一个单链表的头节点 head ，让你反转链表，然后把反转后的链表返回。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中的节点数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：你可以尝试用迭代或者递归两种方式来实现反转。你能用两种方法来做吗？
思路及解答
双指针解法（迭代解法）
反转链表，最简单的办法就是改变链表的 next 指针，不用另开辟新的链表。这样既节省空间，又能做到快速反转。
如图所示，假设链表的原头是元素1，反转后就变成了元素5做头节点。你会发现，链表的节点没变，但 next 指针指向的方向发生了变化。
具体步骤：
- 先定义一个
cur指针指向头节点，另定义一个pre指针初始化为null。 - 然后通过一个循环，每次保存当前节点的
next指针，把cur节点的next指向pre，实现反转。 - 不断移动
pre和cur指针，直到cur变成null。 - 最后，返回
pre指针，它指向了新的头节点。
// 双指针解法
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 定义三个指针
ListNode prev = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next; // 保存下一个节点
cur.next = prev; // 当前节点指向prev
prev = cur; // prev移动到cur
cur = temp; // cur移动到下一个节点
}
return prev; // prev会指向反转后的头节点
}
}
上面这段代码逻辑虽然不复杂，但在处理指针时有一些小技巧，能让你的思路更清晰。要注意循环的终止条件，明确每个指针的位置，这样能保证你最终能拿到正确的答案。如果还是觉得抽象，可以通过画图来模拟指针的移动，理解起来会更直观。
递归解法
说实话，迭代解法操作起来简单直接，但如果让你尝试递归，怎么解决这个问题呢？其实这就像解二叉树问题一样，递归思维一旦开启，就能很轻松地解决。
递归反转链表的核心思路是“分治”，把大问题分解成小问题来解决。
比如，给定链表 1->2->3->4，如果我们反转掉 2->3->4 这部分，再把节点1连接到反转后的链表上，那就能实现整个链表的反转了。
这样递归的基本思路就是：
reverseList(1->2->3->4) = reverseList(2->3->4) -> 1
class Solution {
// 定义递归函数
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next); // 递归反转剩余链表
head.next.next = head; // 反转当前节点
head.next = null; // 断开当前节点的next指针
return last; // 返回新的头结点
}
}
递归解法看起来更简洁一些，不过要注意，递归的调用栈可能会在链表很长的情况下导致栈溢出。
借用栈的解法
你也可以使用栈来反转链表，栈的特点就是“先进后出”。借助栈，我们可以把所有节点都放进去，然后再按顺序取出，完成反转。
操作步骤是这样的：
- 把所有节点依次入栈。
- 创建一个虚拟头结点，用
cur指针指向它。 - 开始出栈，每出一个栈顶元素，就把它加到链表中，最后返回反转后的链表。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
if (head.next == null) return head;
ArrayDeque<ListNode> stack = new ArrayDeque<>();
ListNode cur = head;
// 将所有节点入栈
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 创建虚拟头结点
ListNode pHead = new ListNode(0);
cur = pHead;
// 开始出栈并构建新链表
while (!stack.isEmpty()) {
ListNode node = stack.pop();
cur.next = node;
cur = cur.next;
}
// 最后一个节点的next指向null
cur.next = null;
return pHead.next;
}
}
栈的方法适用于小规模的数据，但如果链表非常长，栈的空间复杂度会变得比较高，可能会出现性能问题。
解法总结
总的来说，最常用的反转链表方法是双指针的迭代解法，因为它既简单又节省空间。递归和栈的方法虽然也能解决问题，但在链表非常长时，可能会遇到栈溢出的问题，性能也不如迭代解法。