反转链表（全反转与区间反转）

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

题目描述

问题一:反转整个链表(LeetCode 206)

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

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

问题二:反转链表的某一段(LeetCode 92)

给你单链表的头节点 head 和两个整数 left、right(1 ≤ left ≤ right ≤ n),请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
解释：只把第 2~4 个节点 (2→3→4) 反转成 (4→3→2)，其余不动

两道题共享同一个内核:如何把一串节点的指针方向逐个"掉头"。掌握了全反转的双指针写法,区间反转不过是"先定位边界,再对中间那段做同样的事,最后把首尾接回去"。

思路拆解

暴力解法:借助额外数组

最直觉的想法:遍历链表把所有值存进数组,再倒序重建链表(或倒序赋值)。

点击展开暴力解法（不推荐）

// 把值搬进数组 → 倒序写回链表
function reverseList(head) {
  const vals = [];
  let node = head;
  while (node) { vals.push(node.val); node = node.next; }

  node = head;
  for (let i = vals.length - 1; i >= 0; i--) {
    node.val = vals[i]; // 只改值，不动指针
    node = node.next;
  }
  return head;
}

为什么暴力解法不好？

它额外开了一个长度为 的数组,空间复杂度 。而且它只是"搬运数值",并没有真正训练到链表指针操作的核心——改变 next 指向。面试中考察的正是后者。

最优解法:双指针原地反转(问题一)

核心动作只有一句话:让当前节点的 next 指回它的前驱。为此我们维护三个指针:

• prev:已反转部分的头(初始为 null,因为原头节点反转后 next 应指向 null);
• curr:当前正在处理的节点;
• next:临时保存 curr.next,防止改指针后"断链找不到后面"。

核心思路

每一步做四件事,顺序不能乱:

1. next = curr.next —— 先存好后继,否则下一步改了 curr.next 就再也找不到它;
2. curr.next = prev —— 掉头,当前节点指向前驱;
3. prev = curr —— 前驱前移;
4. curr = next —— 当前指针前移。

用指针滑动表示:每轮 prev 和 curr 同步向右挪一格,直到 curr 走出链表(变成 null),此时 prev 就是新的头。可以把它想成"翻绳子":

递归写法（同为最优，理解方向即可）

// 递归到底再逐层掉头，空间 O(n)（递归栈）
function reverseList(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverseList(head.next); // 先反转后面
  head.next.next = head; // 让后继指回自己
  head.next = null;      // 自己断开原来的指向
  return newHead;
}

最优解法:区间反转(问题二)

区间反转 = 定位边界 + 局部反转 + 首尾缝合。为了让"反转段的前一个节点"这一边界统一好处理(尤其 left = 1 时前面没有节点),我们引入哑节点 dummy。

区间反转的"穿针引线"法

1. 建哑节点 dummy.next = head,让 prev 停在反转段的前一个位置(走 left - 1 步);
2. 令 curr = prev.next(反转段的第一个节点,反转完它会变成这段的尾巴);
3. 执行 right - left 次"头插":每次把 curr 的下一个节点 next 摘下来,插到 prev 的正后方;
4. prev 始终不动,curr 也不动(它随着别人被插到前面而自然后移),循环结束整段就反转好了。

头插法的三行核心:

交互式动画演示

下面用样例 head = [1,2,3,4,5] 演示全链表反转的双指针全过程。点击 下一步 观察 prev、curr、next 三指针的移动与每个节点 next 的掉头:

步骤 1 / 16初始化

已反转 (prev 侧)

null

待处理 (curr 侧)

curr

1

→

2

→

3

→

4

→

5

→

null

初始化：prev = null（已反转部分为空），curr 指向头节点 1。目标是让每个节点的箭头逐个掉头。

完整代码(JavaScript)

问题一:反转整个链表

高亮行为双指针四步核心。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
  let prev = null;   // 已反转部分的头，初始为 null
  let curr = head;   // 当前处理节点

  while (curr) {
    const next = curr.next; // 1. 暂存后继，防止断链
    curr.next = prev;       // 2. 掉头：指向前驱
    prev = curr;            // 3. 前驱前移
    curr = next;            // 4. 当前前移
  }

  return prev; // curr 为 null 时，prev 即新头
}

问题二:反转区间 [left, right]

高亮行为头插法核心四步。

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
function reverseBetween(head, left, right) {
  const dummy = new ListNode(0, head); // 哑节点，统一边界
  let prev = dummy;

  // 1. 让 prev 走到反转段前一个节点
  for (let i = 0; i < left - 1; i++) prev = prev.next;

  // 2. curr 为反转段第一个节点（反转后会成为尾）
  const curr = prev.next;

  // 3. 头插 right - left 次
  for (let i = 0; i < right - left; i++) {
    const next = curr.next;        // 摘下 curr 的下一个
    curr.next = next.next;         // curr 跨过 next
    next.next = prev.next;         // next 插到最前
    prev.next = next;              // prev 指向 next
  }

  return dummy.next;
}

复杂度分析

设链表长度为 ,区间反转中 为待反转段长度。

解法	时间复杂度	空间复杂度	说明
暴力(数组)			额外数组存全部值
双指针全反转			一趟遍历,只用常数指针
递归全反转			递归调用栈深度为
区间头插反转			定位 + 反转 ,合计一趟

边界与易错点

常见踩坑

1. 忘记暂存 next:先写 curr.next = prev 再取 curr.next,会导致链表在此断裂、后面全部丢失。顺序必须是先存后继,再掉头。
2. 返回错指针:全反转应返回 prev(不是 curr,循环结束时 curr 已是 null)。
3. 区间反转不用哑节点:当 left = 1 时反转段前面没有节点,不加哑节点就要为此写特判,容易出错。哑节点让 prev 永远有落脚点。
4. 头插循环次数写错:应循环 right - left 次(而非 right - left + 1),因为第一个节点 curr 是被"绕过"的支点,不参与头插动作。
5. 空链表 / 单节点:head 为 null 或只有一个节点时,全反转直接返回原 head 即可,双指针写法天然覆盖此情况(循环不进入或只进入一次)。
6. 递归写法的栈溢出:链表极长时递归深度 可能爆栈,生产环境优先用迭代双指针。

一句话总结

全反转:三指针 prev/curr/next,先存后继再掉头;区间反转:哑节点定位 + 头插法穿针引线。 两者内核一致,记住"先暂存,防断链"这条铁律。