1. 简介
在计算机科学中，链表（Linked List） 是一种线性数据结构，其中每个节点通过指针链接到下一个节点。本文将介绍如何反转一个链表，并提供两种实现方式：迭代和递归。
2. 链表反转概念
链表中的每个节点包含两个部分：
- 数据域（data）
- 指针域（next），指向下一个节点
我们通常使用一个 head 指针指向链表的第一个节点：
反转后，head 指针将指向原链表的最后一个节点，且每个节点的 next 指针指向其前一个节点：
3. 迭代解法
我们先考虑一个简化的情况：反转两个节点。
假设当前节点为 current，前一个节点为 previous，我们可以执行以下操作：
current.next = previous;
previous.next = null; // 原始链表中没有这个操作，仅为示例
对于更长的链表，我们只需遍历整个链表，并在每一步中反转当前节点的指针：
public ListNode reverseListIteratively(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode nextElement = current.next;
current.next = previous;
previous = current;
current = nextElement;
}
return previous;
}
✅ 解法说明：
- 使用三个指针：
previous、current和nextElement - 每次迭代中，先保存
nextElement，然后反转current.next指向previous - 最后
previous会成为新链表的头节点
⏱️ 时间复杂度：
- **O(n)**，其中 n 是链表节点数，每个节点只被访问一次
⚠️ 踩坑提醒：
- 一定要保存
nextElement，否则反转后会丢失对下一个节点的引用
4. 递归解法
递归解法的核心思想是：先递归反转后续节点，再处理当前节点的反转。
例如，我们已经递归处理了 head.next 之后的所有节点，此时链表如下：
我们只需处理两个节点：head 和 head.next：
head.next.next = head;
head.next = null;
递归实现如下：
public ListNode reverseListRecursively(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode node = reverseListRecursively(head.next);
head.next.next = head;
head.next = null;
return node;
}
✅ 解法说明：
- 基础条件：空链表或只有一个节点时直接返回
- 递归调用
reverseListRecursively(head.next)反转后续节点 - 反转当前节点与下一个节点的连接
⏱️ 时间复杂度：
- **O(n)**，每个节点也只被访问一次
⚠️ 踩坑提醒：
- 递归深度过大会导致栈溢出（Stack Overflow），在处理非常长的链表时要小心
5. 总结
本文介绍了如何使用迭代和递归两种方式反转链表：
| 方法 | 时间复杂度 | 是否需要额外空间 | 是否容易理解 |
|---|---|---|---|
| 迭代 | ✅ O(n) | ✅ O(1) | ✅ 是 |
| 递归 | ✅ O(n) | ❌ O(n)（调用栈） | ❌ 否 |
✅ 推荐使用迭代方式，尤其在链表较长或对性能敏感的场景下。
⚠️ 递归适合教学或链表较短的场景，但要注意栈溢出问题。