.jpg)
536 字
3 分钟
反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路
- 迭代反转：
- 使用三个指针：prev（前驱）、curr（当前）、next（后继）
- 遍历链表，逐个反转节点指向
- 递归反转：
- 递归到链表末端开始回溯
- 回溯过程中反转节点指向
- 头插法：
- 新建哑节点作为新链表头
- 遍历原链表，逐个插入新链表头部
- 就地反转：
- 直接在原链表上修改指针
- 终止条件：
- 迭代：curr 为空时结束
- 递归：到达尾节点返回
关键洞察
- 指针保存：
- 反转前必须保存 next 指针防断链
- 顺序关键：
- 迭代顺序：保存 next → 反转 curr → 移动 prev → 移动 curr
- 递归本质：
- 递归栈隐式保存节点关系
- 尾递归优化：
- 递归反转可转为迭代提高效率
- 哑节点技巧：
- 头插法中使用哑节点简化操作
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 迭代 | O(n) | O(1) |
| 递归 | O(n) | O(n) (栈空间) |
| 头插法 | O(n) | O(1) |
代码实现
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var reverseList = function (head) { let pre = null, cur = head; while (cur) { const next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre;};变种：反转部分链表
def reverseBetween(head, m, n): if not head or m == n: return head
dummy = ListNode(0, head) pre = dummy
# 移动到反转起始点 for _ in range(m - 1): pre = pre.next
# 反转m到n部分 curr = pre.next for _ in range(n - m): next_node = curr.next curr.next = next_node.next next_node.next = pre.next pre.next = next_node
return dummy.next实际应用场景
- 浏览器历史：实现前进/后退功能`
- 撤销操作：文本编辑器的undo/redo`
- 回文检测：反转链表与原始链表比较`
- 链表重排：L0→L1→…→Ln → L0→Ln→L1→Ln-1…`