LeetCode 难度为 Hard 的经典链表题——25. K个一组翻转链表，这道题是链表翻转的进阶题，考察对链表指针操作的熟练度，也是面试中的高频考点，很多人会在“组内翻转”“组间连接”“边界处理”上踩坑。

今天不仅会讲解题目核心，还会对比两份不同思路的代码，分析它们的优缺点、避坑点，帮大家彻底吃透这道题，下次遇到直接秒解！

一、题目解读（清晰易懂版）

题目核心需求很明确，一句话概括：给一个链表，每k个节点当成一组，组内翻转；如果最后剩下的节点不足k个，就保持原样。

关键约束（必看，避坑前提）：

• k是正整数，且k ≤ 链表长度（不用考虑k大于链表长度的情况）；

• 不能只改节点的值，必须实际交换节点（排除“偷巧”解法）；

• 组间顺序不变，只有组内节点翻转（比如链表1->2->3->4，k=2，结果是2->1->4->3，不是4->3->2->1）。

示例辅助理解：

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

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

• 输入：head = [1,2], k = 2 → 输出：[2,1]

二、链表节点定义（题目给出，直接复用）

先贴出题目给出的ListNode定义，两份解法都基于这个结构，不用额外修改：

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

三、两种解法详解对比

下面分别讲解两份代码（reverseKGroup_1 和 reverseKGroup_2），从思路、执行流程、优缺点三个维度拆解，帮大家看清两种思路的差异。

解法一：reverseKGroup_1（全局翻转+局部调整+回滚，新手易上手但需避坑）

1. 核心思路

这种思路的核心是「边遍历边全局翻转，每凑够k个节点，就调整一次组间连接；最后如果不足k个节点，再把这部分翻转回去」。

可以类比成：把链表当成一串珠子，从头开始逐个翻转（珠子顺序颠倒），每翻k个，就把这k个珠子“固定”到正确的位置（连接好前后组）；如果最后剩的珠子不够k个，就把这几个珠子再翻回来，恢复原样。

2. 关键变量说明

• dummy：虚拟头节点，避免处理头节点翻转的特殊情况（所有链表题的通用技巧）；

• preGroup：每组翻转的“前置节点”，负责连接上一组的尾和当前组的头；

• prev：翻转节点时的“前驱节点”，记录当前节点的前一个节点（用于翻转指针）；

• curr：当前正在遍历、翻转的节点；

• count：组内节点计数器，用于判断是否凑够k个节点。

3. 代码执行流程（以 head=[1,2,3,4], k=2 为例）

1. 初始状态：dummy(0)->1->2->3->4，preGroup=dummy，prev=dummy，curr=1，count=0；

2. 遍历curr=1：count≠2，翻转1（1.next=prev=dummy），prev=1，curr=2，count=1；

3. 遍历curr=2：count≠2，翻转2（2.next=prev=1），prev=2，curr=3，count=2；

4. 凑够k=2个节点：调整组间连接——preGroup.next=prev=2（dummy->2），原组头lastNode=1，1.next=curr=3（2->1->3）；更新preGroup=1，prev=1，count=0；

5. 继续遍历curr=3：重复步骤2-3，翻转3、4，凑够k=2个节点，调整连接（1->4，3.next=null）；

6. 循环结束，count=0，无不足k个的节点，返回dummy.next=2，最终结果2->1->4->3（正确）。

4. 优点&缺点

优点：思路直观，新手容易理解（只需要掌握“单个节点翻转”的基础操作，再加上计数和回滚）；代码结构清晰，逐步骤执行，容易调试。

缺点：存在冗余逻辑（比如单独处理“最后一组刚好k个节点”的else if分支）；过度使用空值断言（!），有潜在空指针风险；最后回滚步骤增加了少量时间开销（虽然时间复杂度还是O(n)）。

5. 核心避坑点

• 避免链表环：翻转后必须及时调整组尾的next指针（lastNode.next=curr），否则会出现“dummy<->1”的环，触发运行错误；

• 回滚逻辑不能漏：如果最后剩余节点不足k个，必须把这部分翻转的节点再翻回来，否则会破坏原有顺序；

• 空值判断：preGroup.next不可能为null，可移除多余的空值判断，避免错误返回null。

解法二：reverseKGroup_2（先找组边界+组内单独翻转，最优解法）

这是更推荐的解法，也是面试中更常考的思路——「先找每组的边界（头和尾），确认够k个节点后，再单独翻转这组节点；组间连接直接通过边界节点处理，无需回滚」。

类比：还是一串珠子，先找到前k个珠子（确定组头和组尾），把这k个珠子单独翻转，再连接好前后珠子；再找下k个珠子，重复操作；如果找不到k个，就直接结束，不用再调整。

1. 关键变量说明（新增/差异变量）

• groupTail：当前组的尾节点，通过移动k次找到，同时判断剩余节点是否够k个；

• groupHead：当前组的头节点（翻转后会变成组尾）；

• nextGroupHead：下一组的头节点，提前记录，避免翻转后找不到下一组。

2. 代码执行流程（以 head=[1,2,3,4], k=2 为例）

1. 初始状态：dummy(0)->1->2->3->4，preGroup=dummy；

2. 找第一组边界：groupTail从preGroup开始移动2次，找到groupTail=2（确认够k个节点）；记录groupHead=1，nextGroupHead=3；

3. 单独翻转当前组（1->2）：prev初始化为nextGroupHead=3，curr=groupHead=1；循环翻转，直到curr=nextGroupHead，翻转后变成2->1；

4. 连接组间：preGroup.next=groupTail=2（dummy->2），preGroup更新为groupHead=1（下一组的前置节点）；

5. 找第二组边界：groupTail从preGroup=1移动2次，找到groupTail=4；记录groupHead=3，nextGroupHead=null；

6. 单独翻转当前组（3->4），连接组间；

7. 下一次找组边界：移动不足2次，count<k，直接返回dummy.next=2，结果2->1->4->3（正确）。

3. 优点&缺点

优点：逻辑更高效，无需回滚（提前判断节点数量，不足k个直接返回）；无冗余分支，代码更简洁；指针操作更严谨，避免链表环和空指针风险；时间复杂度O(n)，空间复杂度O(1)，是最优解法。

缺点：对指针操作的熟练度要求更高，需要提前规划好“找边界-翻转-连接”的流程，新手可能需要多调试几次才能理解。

4. 核心避坑点

• 找组边界时，必须同时判断节点数量：移动k次后，如果groupTail.next不存在，说明不足k个节点，直接返回；

• 翻转组内节点时，prev初始化为nextGroupHead：这样翻转后，组尾（原groupHead）的next会自动指向nextGroupHead，无需额外调整；

• preGroup更新为原groupHead：翻转后，原groupHead变成组尾，作为下一组的前置节点，保证组间连接正确。

四、两份代码对比总结

对比维度	reverseKGroup_1	reverseKGroup_2
核心思路	全局翻转+组间调整+不足k个回滚	先找组边界+组内单独翻转+无回滚
时间复杂度	O(n)（回滚最多增加O(k)，可忽略）	O(n)（最优，每个节点只遍历一次）
空间复杂度	O(1)	O(1)
可读性	高，新手易理解	中等，需熟练掌握指针操作
适用场景	新手刷题、快速调试	面试、生产环境（最优解）
潜在坑点	链表环、回滚遗漏、空值断言	组边界判断、prev初始化

五、刷题建议&拓展思考

1. 刷题建议

• 新手：先吃透 reverseKGroup_1，掌握“翻转+计数+回滚”的思路，熟练后再过渡到 reverseKGroup_2；

• 进阶：重点练习 reverseKGroup_2，尝试自己手写“找边界-翻转-连接”的流程，避免依赖模板；

• 调试技巧：遇到指针混乱时，画链表结构图（比如用草稿纸写出每个节点的next指向），逐步骤跟踪指针变化，比单纯看代码更高效。

2. 拓展思考（面试高频追问）

• 如果k可以大于链表长度，该如何修改代码？（提示：在找组边界时，判断count是否等于链表长度，不足则不翻转）；

• 如何用递归实现K个一组翻转链表？（提示：递归终止条件是剩余节点不足k个，递归逻辑是翻转当前组，再递归翻转下一组）；

• 如果要求“每k个节点一组翻转，不足k个节点时全部翻转”，该如何修改？（提示：移除回滚逻辑，或不判断节点数量，直接翻转）。

六、最终优化版代码（推荐面试使用）

基于 reverseKGroup_2 优化，移除空值断言，增加防御性判断，代码更健壮、简洁，适配面试场景：

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  if (k === 1 || !head || !head.next) return head;

  const dummy = new ListNode(0, head);
  let preGroup = dummy; // 每组翻转的前置节点
  let count = 0;

  while (true) {
    // 第一步：找组尾，判断剩余节点是否够k个
    let groupTail = preGroup;
    count = 0;
    while (count < k && groupTail.next) {
      groupTail = groupTail.next;
      count++;
    }
    if (count < k) return dummy.next; // 不足k个，直接返回

    // 第二步：记录关键节点
    const groupHead = preGroup.next;
    const nextGroupHead = groupTail.next;

    // 第三步：组内翻转
    let prev: ListNode | null = nextGroupHead;
    let curr = groupHead;
    while (curr !== nextGroupHead) {
      const next = curr?.next;
      if (curr) curr.next = prev;
      prev = curr;
      curr = next;
    }

    // 第四步：组间连接
    preGroup.next = groupTail;
    preGroup = groupHead!;
  }
}

七、总结

LeetCode 25题的核心是「组内翻转+组间连接」，两种解法的本质都是通过指针操作实现，但思路的高效性有差异。

无论哪种解法，都要记住三个核心要点：① 用虚拟头节点简化头节点处理；② 明确每组的边界（头、尾、下一组头）；③ 翻转时避免链表环和空指针。

刷题不是背代码，而是理解思路、掌握技巧。建议大家多调试、多画图，熟练掌握指针操作，下次遇到类似的链表翻转题（比如两两翻转、指定区间翻转），就能举一反三、轻松应对！

反转链表是链表类题目中的基础题型，但 LeetCode 92 题「反转链表II」并非完整反转整个链表，而是反转链表中指定区间 [left, right] 的节点，这道题更考验对链表指针操作的精细化控制，也是面试中高频出现的变形题。今天就带大家一步步拆解这道题，从题意理解到代码实现，再到易错点规避，帮大家彻底搞懂。

一、题目大意

给定一个单链表的头节点 head，以及两个整数 left 和 right（满足 left ≤ right），要求只反转链表中「从第 left 个节点到第 right 个节点」的部分，反转后保持链表其余部分的顺序不变，最终返回修改后的链表头节点。

举个简单例子帮助理解：

• 输入：head = [1,2,3,4,5], left = 2, right = 4

• 反转区间 [2,4] 的节点（即 2→3→4 反转为 4→3→2）

• 输出：[1,4,3,2,5]

二、核心难点分析

这道题的难点不在于「反转」本身（完整反转链表的双指针法大家基本都能掌握），而在于「局部反转」的边界处理：

1. 如何精准定位到 left 节点的前驱节点（记为 leftPreNode）和 right 节点的后继节点（记为 temp）？这两个节点是连接「未反转部分」和「反转部分」的关键，一旦处理不好就会出现链表断裂。

2. 反转区间内的节点时，如何保证指针迭代不混乱？反转过程中 prev、curr 指针的移动的顺序，直接影响反转是否正确。

3. 边界场景的处理：比如 left = 1（反转从表头开始）、left = right（无需反转）、链表长度等于 right（反转到表尾）等情况。

三、解题思路（迭代双指针法，最易理解）

针对局部反转的特点，我们采用「先定位边界，再反转区间，最后连接边界」的三步走策略，同时使用「虚拟头节点」规避表头反转的特殊处理，具体步骤如下：

步骤1：创建虚拟头节点（dummy node）

为什么要创建虚拟头节点？因为如果 left = 1，反转的是从表头开始的部分，此时我们需要一个前驱节点来连接反转后的新表头。虚拟头节点 dummy 的 val 可以设为 0，next 指向原表头 head，这样无论 left 是否为 1，我们都能统一处理 left 的前驱节点。

步骤2：定位边界节点

使用两个指针 prev 和 curr，从虚拟头节点开始迭代，找到以下三个关键节点：

• leftPreNode：第 left 个节点的前驱节点（反转后需要它连接反转区间的新表头）；

• reverseStart：第 left 个节点（反转区间的原表头，反转后会变成区间的表尾）；

• curr 最终移动到第 right 个节点（反转区间的原表尾，反转后会变成区间的新表头）。

步骤3：反转 [left, right] 区间内的节点

这一步和「完整反转链表」的双指针逻辑一致：用 temp 暂存 curr 的下一个节点，然后让 curr 指向 prev（实现反转），再依次移动 prev 和 curr 指针，直到 curr 超出反转区间。

步骤4：连接边界，修复链表

反转完成后，需要将反转区间与原链表的其余部分重新连接：

• 反转区间的原表头（reverseStart），现在要指向 right 节点的后继节点（temp）；

• left 的前驱节点（leftPreNode），现在要指向反转区间的新表头（原 right 节点）。

步骤5：返回结果

最终返回 dummy.next 即可（因为 dummy 是虚拟头节点，其 next 才是修改后链表的真实表头）。

四、完整代码实现（TypeScript）

结合上面的思路，附上完整可运行的 TypeScript 代码，每一行都添加了详细注释，新手也能轻松看懂：

// 链表节点类定义（题目已给出，此处复用）
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val) // 节点值默认0
    this.next = (next === undefined ? null : next) // next指针默认null
  }
}

/**
 * 反转链表中从left到right的节点
 * @param head 链表头节点
 * @param left 反转起始位置（从1开始计数）
 * @param right 反转结束位置（从1开始计数）
 * @returns 反转后的链表头节点
 */
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
  // 1. 创建虚拟头节点，避免left=1时的特殊处理
  const dummy = new ListNode(0, head);
  let curr = head; // 当前遍历的节点
  let prev: ListNode | null = dummy; // 当前节点的前驱节点（初始指向虚拟头）
  let i = 1; // 计数，标记当前节点是第几个（从1开始，和题目位置一致）
  
  let leftPreNode: ListNode | null = null; // left节点的前驱节点
  let reverseStart: ListNode | null = null; // left节点（反转区间的原表头）

  // 2. 遍历链表，定位边界节点并反转区间
  while (curr) {
    if (i < left || i > right) {
      // 情况1：当前节点不在反转区间，直接移动指针
      prev = curr;
      curr = curr.next;
    } else if (i === left) {
      // 情况2：找到反转起始位置left，记录关键节点
      leftPreNode = prev; // 保存left的前驱
      reverseStart = curr; // 保存反转区间的原表头
      // 移动指针，准备开始反转
      prev = curr;
      curr = curr.next;
    } else if (i === right) {
      // 情况3：找到反转结束位置right，处理反转的最后一步
      const temp: ListNode | null = curr.next; // 暂存right的后继节点（避免断裂）
      curr.next = prev; // 反转当前节点的指针
      
      // 连接反转区间与原链表
      if (reverseStart) reverseStart.next = temp; // 原表头指向right的后继
      if (leftPreNode) leftPreNode.next = curr; // left的前驱指向原right（新表头）
      
      // 移动指针，退出循环（后续节点无需处理）
      prev = curr;
      curr = temp;
    } else {
      // 情况4：当前节点在反转区间内，执行常规反转操作
      const temp: ListNode | null = curr.next; // 暂存下一个节点
      curr.next = prev; // 反转指针：当前节点指向前驱
      // 移动指针，继续下一个节点的反转
      prev = curr;
      curr = temp;
    }
    i++; // 计数递增
  }

  // 3. 返回虚拟头节点的next（真实表头）
  return dummy.next;
};

五、关键细节与易错点提醒

这道题很容易在细节上出错，分享几个高频易错点，帮大家避坑：

易错点1：计数从1开始

题目中 left 和 right 是「从1开始计数」的（比如链表 [1,2,3]，left=1 就是第一个节点），所以我们的计数变量 i 要从1开始，而不是0，否则会定位错误。

易错点2：暂存后继节点

反转节点时，一定要先用 temp 暂存 curr.next，再修改 curr.next 的指向。如果直接修改 curr.next = prev，会丢失 curr 的下一个节点，导致链表断裂，无法继续遍历。

易错点3：边界节点的非空判断

代码中判断 if (reverseStart) 和 if (leftPreNode)，是为了避免空指针异常。比如当 left=1 时，leftPreNode 其实是 dummy（非空）；但如果链表为空，或者 left 超出链表长度，这些节点可能为 null，必须判断后再操作。

易错点4：反转后的连接顺序

反转完成后，必须先让 reverseStart.next = temp（连接反转区间的尾部和原链表的后续部分），再让 leftPreNode.next = curr（连接原链表的前部和反转区间的头部）。顺序颠倒不会报错，但会导致链表连接错误。

六、总结

LeetCode 92 题的核心是「局部反转 + 边界连接」，解题的关键在于：

1. 用虚拟头节点简化表头反转的特殊处理；

2. 精准定位 left 的前驱、反转区间的首尾节点；

3. 反转过程中注意指针的移动顺序和暂存操作；

4. 反转后正确连接边界，避免链表断裂。

这道题的迭代法时间复杂度是 O(n)（只需遍历链表一次），空间复杂度是 O(1)（仅使用几个指针变量），是最优解法。建议大家多手动模拟几遍指针移动过程，熟悉链表操作的细节，后续遇到类似的局部反转、指定节点操作等题目，就能举一反三了。

LeetCode 中等难度题目「138. 随机链表的复制」，这道题是链表操作里的经典题型，核心难点在于「随机指针」的复制——常规链表复制只需按顺序处理 next 指针，但随机指针可指向任意节点（包括自身、null 或链表中其他节点），很容易出现“复制节点的随机指针指向原链表节点”的错误，或是陷入重复创建、指针混乱的坑。

先明确题目要求，避免踩坑：

• 深拷贝：复制出 n 个全新节点，不能复用原链表的任何节点

• 指针对应：新节点的 next、random 指针，必须指向复制链表中的节点（而非原链表）

• 状态一致：原链表中 X.random → Y，复制链表中对应 x.random → y

• 输入输出：仅传入原链表头节点，返回复制链表头节点（题目中 [val, random_index] 是输入输出的便捷表示，代码中无需处理索引，直接操作节点）

先贴出题目给出的节点定义（TypeScript 版本），后续两种解法均基于此：

class _Node {
  val: number
  next: _Node | null
  random: _Node | null

  constructor(val?: number, next?: _Node, random?: _Node) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
    this.random = (random === undefined ? null : random)
  }
}

下面分享两种工业界常用的最优解法，分别是「哈希表映射法」和「原地插入拆分法」，各有优劣，大家可根据场景选择。

解法一：哈希表映射法（直观易懂，空间换时间）

核心思路

核心是用「哈希表（Map）」建立「原节点 → 复制节点」的映射关系，解决“复制节点找不到对应随机指针指向”的问题。

两步走：

1. 第一次遍历原链表：只创建复制节点，不处理指针，将原节点作为 key、复制节点作为 value 存入 Map，此时复制节点仅初始化了 val 值。

2. 第二次遍历原链表：根据 Map 中的映射关系，给复制节点赋值 next 和 random 指针——原节点的 next 对应复制节点的 next，原节点的 random 对应复制节点的 random（均从 Map 中取出）。

举个简单例子：原链表 A → B（A.random → B），第一次遍历存 Map(A: A', B: B')；第二次遍历，A'.next = Map.get(A.next) = B'，A'.random = Map.get(A.random) = B'，完美对应原链表状态。

完整代码

function copyRandomList_1(head: _Node | null): _Node | null {
  // 边界处理：空链表直接返回null
  if (!head) {
    return null
  }
  // 建立原节点到复制节点的映射
  const map = new Map()
  let curr: _Node | null = head
  // 第一步：遍历原链表，创建复制节点并存入Map
  while (curr) {
    map.set(curr, new _Node(curr.val))
    curr = curr.next
  }
  // 第二步：遍历原链表，给复制节点赋值next和random
  const dummy = new _Node() // 虚拟头节点，简化边界处理
  curr = head
  let prev = dummy // 记录复制链表的前驱节点
  while (curr) {
    const node = map.get(curr) // 取出当前原节点对应的复制节点
    prev.next = node; // 前驱节点指向当前复制节点
    // 处理random指针：原节点random存在，则复制节点random取Map中对应的值，否则为null
    if (curr.random) {
      node.random = map.get(curr.random)
    }
    // 移动指针，继续遍历
    prev = node;
    curr = curr.next;
  }
  // 虚拟头节点的next就是复制链表的头节点
  return dummy.next;
};

优劣势分析

✅ 优势：思路直观，代码简洁，容易理解和调试，无需操作原链表结构，不易出错。

❌ 劣势：使用了额外的哈希表，空间复杂度 O(n)（n 为链表长度），需要存储所有原节点和复制节点的映射关系。

适用场景：日常开发中，空间复杂度要求不高，优先追求代码可读性和开发效率的场景。

解法二：原地插入拆分法（空间最优，无额外哈希表）

核心思路

如果要求空间复杂度 O(1)（不使用额外哈希表），就需要用「原地插入+拆分」的思路——将复制节点插入到原节点的后面，利用原链表的指针关系，直接找到复制节点的 random 指向，最后再将原链表和复制链表拆分。

三步走（关键在于“插入”和“拆分”的边界处理）：

1. 原地插入复制节点：遍历原链表，在每个原节点 curr 后面插入一个复制节点 newNode（val 与 curr 一致），此时原链表变为「curr → newNode → curr.next（原next）」，不处理 random 指针。

2. 给复制节点赋值 random：再次遍历原链表，当前原节点 curr 的复制节点是 curr.next，而 curr.random 的复制节点是 curr.random.next（因为第一步已在所有原节点后插入了复制节点），直接赋值即可。

3. 拆分两个链表：最后遍历原链表，将原节点和复制节点拆分——原节点的 next 指向自身的下下个节点（跳过复制节点），复制节点的 next 指向自身的下下个节点（复制链表的下一个节点），最终得到独立的复制链表。

关键细节：拆分时要注意链表尾部的边界（当 next 为 null 时，复制节点的 next 也需设为 null），避免出现空指针错误。

完整代码

function copyRandomList_2(head: _Node | null): _Node | null {
  // 边界处理：空链表直接返回null
  if (!head) {
    return null;
  }

  // 第一步：原地插入复制节点（每个原节点后面插一个复制节点）
  let curr: _Node | null = head;
  while (curr) {
    const newNode = new _Node(curr.val); // 创建复制节点
    const nextNode: _Node | null = curr.next; // 保存原节点的next
    curr.next = newNode; // 原节点指向复制节点
    newNode.next = nextNode; // 复制节点指向原节点的原next
    curr = nextNode; // 移动到下一个原节点
  }

  // 第二步：给复制节点赋值random指针
  curr = head;
  while (curr) {
    const newNode: _Node | null = curr.next; // 当前原节点对应的复制节点
    if (newNode) {
      // 原节点random存在 → 复制节点random = 原random的复制节点（原random.next）
      if (curr.random) {
        newNode.random = curr.random.next;
      } else {
        newNode.random = null; // 原random为null，复制节点也为null
      }
      curr = newNode.next; // 移动到下一个原节点（跳过复制节点）
    }
  }

  // 第三步：拆分原链表和复制链表
  curr = head;
  const copyHead = head.next; // 复制链表的头节点（原头节点的下一个）
  while (curr) {
    const newNode: _Node | null = curr.next; // 当前原节点对应的复制节点
    if (newNode) {
      const nextOldNode: _Node | null = newNode.next; // 保存下一个原节点
      curr.next = nextOldNode; // 原节点指向自身的下下个节点（拆分原链表）
      // 复制节点指向自身的下下个节点（拆分复制链表）
      if (nextOldNode) {
        newNode.next = nextOldNode.next;
      } else {
        newNode.next = null; // 链表尾部，复制节点next设为null
      }
      curr = nextOldNode; // 移动到下一个原节点
    }
  }

  return copyHead; // 返回复制链表的头节点
};

优劣势分析

✅ 优势：空间复杂度 O(1)（仅使用几个指针变量），无额外哈希表，空间最优。

❌ 劣势：思路相对复杂，需要三次遍历，且涉及原链表结构的修改，边界处理容易出错（尤其是拆分环节）。

适用场景：面试中要求优化空间复杂度，或内存资源紧张的场景（如嵌入式开发）。

两种解法对比总结

解法	时间复杂度	空间复杂度	核心优势	适用场景
哈希表映射法	O(n)（两次遍历）	O(n)（哈希表存储映射）	直观易懂，调试方便	日常开发，优先可读性
原地插入拆分法	O(n)（三次遍历）	O(1)（无额外空间）	空间最优	面试优化，内存紧张场景

常见踩坑点提醒

• 踩坑1：复制节点的 random 指针直接指向原链表节点 → 违反深拷贝要求，需通过映射或原地插入找到复制节点。

• 踩坑2：边界处理遗漏 → 空链表、链表尾部（next 为 null）、random 为 null 的情况，需单独判断。

• 踩坑3：原地拆分时，原链表的 next 指针未恢复 → 虽然题目不要求恢复原链表，但会导致原链表结构混乱（严谨开发中需注意）。

• 踩坑4：创建复制节点时，未初始化 next 和 random 为 null → 虽然构造函数有默认值，但建议明确赋值，避免隐式错误。

最后总结

「随机链表的复制」的核心是解决「随机指针的定位」问题，两种解法分别从“空间换时间”和“时间换空间”两个角度给出了最优解：

1. 新手入门优先掌握「哈希表映射法」，代码简洁、思路清晰，能快速解决问题，应对日常开发场景；

2. 面试进阶需掌握「原地插入拆分法」，理解其指针操作逻辑和边界处理，体现对链表操作的深度掌握。

LeetCode 上的经典栈应用题——224. 基本计算器，这道题的核心是实现一个支持 加减运算、括号、空格 的简易计算器，并且明确禁止使用 eval() 等内置表达式计算函数，完全需要我们手动解析字符串、处理运算逻辑。

很多同学遇到这道题会头疼，尤其是括号带来的运算优先级问题，今天就结合完整可运行的代码，从题目理解到代码拆解，一步步讲清楚每一步的逻辑，新手也能轻松看懂！

一、题目回顾（LeetCode 224. 基本计算器）

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意：

• 表达式 s 只包含数字、'+'、'-'、'('、')' 和空格 ' '；

• 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval()；

• 示例：输入 "(1+(4+5+2)-3)+(6+8)"，输出 23；输入 " 2-1 + 2 "，输出 3。

题目核心难点

这道题的难点不在于加减运算本身，而在于两个点：

1. 括号的处理：括号会改变运算优先级，需要先计算括号内的子表达式，再将结果与括号外的内容合并；

2. 多位数的解析：字符串中的数字可能是个位数（如 "1"），也可能是多位数（如 "123"），需要正确拼接；

3. 空格的过滤：空格不影响计算，需要跳过不处理。

二、核心解题思路

解决这道题的最优思路是使用 栈（Stack） 来保存计算过程中的状态，核心逻辑围绕「括号优先级」和「符号处理」展开：

1. 用栈保存括号外的计算状态：遇到左括号 '(' 时，将当前已经计算出的结果、括号前的符号保存到栈中，然后重置状态，专门计算括号内的子表达式；

2. 用变量维护当前计算状态：用 result 记录当前层级（括号内/外）的计算结果，用 sign 记录当前数字的符号（默认是 '+'，因为表达式第一个数字隐含正号），用 num 临时拼接多位数；

3. 遇到右括号 ')' 时，弹出栈中保存的状态（括号外的结果和括号前的符号），将括号内的计算结果与括号外的结果合并，继续后续计算；

4. 空格直接跳过，不影响任何计算逻辑。

简单来说：栈的作用就是「暂存括号外的上下文」，让我们可以专注于括号内的计算，计算完成后再回退到之前的上下文继续运算。

三、完整代码实现（TypeScript）

先上完整可运行的代码，后面逐行拆解每一步逻辑，确保每一行代码都讲明白：

function calculate(s: string): number {
  const stack: number[] = [];
  let num = 0;
  let sign = '+'; // 当前数字的符号（+/-）
  let result = 0; // 当前层级（括号内/外）的计算结果

  for (let i = 0; i < s.length; i++) {
    const c = s[i];

    // 1. 解析多位数（比如"123" -> 123）
    if (c >= '0' && c<= '9') {
      num = num * 10 + (c.charCodeAt(0) - '0'.charCodeAt(0));
    }

    // 2. 处理左括号：保存当前状态（结果、符号）到栈，重置状态计算括号内的值
    if (c === '(') {
      stack.push(result); // 保存括号外的结果
      stack.push(sign === '+' ? 1 : -1); // 保存括号前的符号（用1/-1代替+/-更方便）
      // 重置状态，开始计算括号内的子表达式
      result = 0;
      sign = '+';
    }

    // 3. 处理运算符（+/-）或右括号：结算当前数字
    if ((c === '+' || c === '-') || i === s.length - 1 || c === ')') {
      // 根据当前符号，把数字加到结果中
      result += sign === '+' ? num : -num;
      num = 0; // 重置临时数字

      // 更新符号（仅当是+/-时）
      if (c === '+' || c === '-') {
        sign = c;
      }

      // 4. 处理右括号：弹出栈中保存的状态，合并结果
      if (c === ')') {
        const prevSign = stack.pop()!; // 括号前的符号（1/-1）
        const prevResult = stack.pop()!; // 括号外的结果
        result = prevResult + prevSign * result; // 合并括号内和括号外的结果
      }
    }

    // 空格直接跳过，无需处理
  }

  return result;
}

四、代码逐行拆解（核心逻辑精讲）

我们按「初始化变量 → 遍历字符串 → 各场景处理 → 最终返回结果」的顺序，逐块拆解代码，重点讲清楚栈的用法和括号处理逻辑。

1. 初始化变量（关键变量说明）

const stack: number[] = []; // 栈：保存括号外的计算状态（结果+符号）
let num = 0; // 临时变量：拼接多位数（如"123"，先算1，再12，最后123）
let sign = '+'; // 符号变量：记录当前数字的符号（默认+，因为第一个数字隐含正号）
let result = 0; // 结果变量：记录当前层级（括号内/外）的计算结果

这里有个小细节：sign 记录的是「当前数字的符号」，而不是「上一个运算符」，这样处理能更方便地对接多位数解析和括号逻辑，后面会看到具体作用。

2. 遍历字符串（核心循环）

循环的核心是「逐个处理字符」，根据字符的类型（数字、左括号、右括号、运算符、空格），执行不同的逻辑，我们逐个场景分析：

场景1：解析多位数（字符是 0-9）

if (c >= '0' && c <= '9') {
  num = num * 10 + (c.charCodeAt(0) - '0'.charCodeAt(0));
}

这行代码是「多位数拼接」的关键，举个例子：解析 "123" 时：

• 遇到 '1'：num = 0 * 10 + (49 - 48) = 1（字符 '0' 的 ASCII 码是 48，'1' 是 49）；

• 遇到 '2'：num = 1 * 10 + (50 - 48) = 12；

• 遇到 '3'：num = 12 * 10 + (51 - 48) = 123；

这样就完成了多位数的正确拼接，避免把 "123" 解析成 1、2、3 三个单独的数字。

场景2：处理左括号 '('

if (c === '(') {
  stack.push(result); // 保存括号外的结果
  stack.push(sign === '+' ? 1 : -1); // 保存括号前的符号（用1/-1代替+/-）
  // 重置状态，开始计算括号内的子表达式
  result = 0;
  sign = '+';
}

这是括号处理的核心步骤之一，目的是「暂存括号外的上下文」，举个例子：当遇到表达式 "(1 + 2) - 3" 中的 '(' 时：

1. 此时 result = 0（括号外还没计算），sign = '+'（括号前是正号）；

2. 把 result（0）压入栈，再把 sign 转换成 1（'+' 对应 1，'-' 对应 -1）压入栈；

3. 重置 result = 0、sign = '+'，开始专注计算括号内的 "1 + 2"。

为什么用 1/-1 代替 '+'/'-'？因为后续合并括号内外结果时，直接用「括号外结果 + 括号前符号 × 括号内结果」就能快速计算，无需再判断符号字符串，更简洁。

场景3：处理运算符（+/-）、右括号 ')' 或字符串末尾

这部分是「结算当前数字」的核心，当遇到以下三种情况时，说明当前数字已经解析完成，需要把它加到 result 中：

• 遇到运算符 '+' 或 '-'（下一个数字要开始解析，当前数字需要结算）；

• 遇到右括号 ')'（括号内的数字解析完成，需要结算后和括号外合并）；

• 遍历到字符串末尾（最后一个数字没有后续运算符，需要结算）。

if ((c === '+' || c === '-') || i === s.length - 1 || c === ')') {
  // 步骤1：根据当前符号，把数字加到结果中
  result += sign === '+' ? num : -num;
  num = 0; // 重置临时数字，准备解析下一个数

  // 步骤2：更新符号（仅当当前字符是+/-时）
  if (c === '+' || c === '-') {
    sign = c;
  }

  // 步骤3：处理右括号，合并括号内外结果
  if (c === ')') {
    const prevSign = stack.pop()!; // 弹出括号前的符号（1/-1）
    const prevResult = stack.pop()!; // 弹出括号外的结果
    result = prevResult + prevSign * result; // 合并结果
  }
}

我们分步骤拆解这部分逻辑，还是用例子辅助理解：

例子1：解析 "1 + 2" 时，遇到 '+' 运算符：

• 此时 num = 1（已经解析完第一个数字），sign = '+'；

• result += 1 → result = 1；

• num 重置为 0，sign 更新为 '+'（当前运算符）；

• 继续解析下一个数字 2，后续遇到字符串末尾时，再把 2 加到 result 中，最终 result = 3。

例子2：解析 "(1 + 2) - 3" 时，遇到 ')' 右括号：

• 括号内已经解析完 "1 + 2"，此时 result = 3，num = 0；

• 弹出栈顶的 prevSign = 1（括号前是正号），再弹出 prevResult = 0（括号外的结果）；

• 合并结果：result = 0 + 1 × 3 = 3；

• 继续解析后续的 '-' 和 3，最终 result = 3 - 3 = 0。

场景4：处理空格（直接跳过）

代码中没有专门写空格的处理逻辑，因为当 c 是空格时，不满足任何一个 if 条件，会直接进入下一次循环，相当于「自动跳过」，逻辑简洁高效。

3. 最终返回结果

循环结束后，result 中就保存了整个表达式的计算结果，直接返回即可：return result;

五、总结与优化思考

1. 核心知识点回顾

这道题的核心是「栈的应用」，用栈暂存括号外的上下文，解决括号优先级问题，同时用三个变量（num、sign、result）维护当前计算状态，高效解析多位数和符号。

关键亮点：

• 用 1/-1 代替 '+'/'-' 符号，简化括号内外结果的合并逻辑；

• 一次遍历完成所有解析和计算，时间复杂度 O(n)（n 是字符串长度）；

• 栈的空间复杂度最坏 O(n)（嵌套括号层数最多为 n/2），属于最优解法。

2. 优化方向（可选）

如果想进一步优化代码，可以考虑：

• 用正则表达式先过滤掉所有空格，减少循环中的判断（但会增加一次正则遍历，整体效率影响不大）；

• 对于嵌套括号极深的场景，栈的空间开销无法避免，这是该思路的固有特性，也是最优选择。

3. 刷题启示

遇到「优先级处理」「上下文暂存」类的算法题，优先考虑栈这种数据结构（比如括号匹配、表达式求值等）。这道题虽然是中等难度，但覆盖了栈的核心用法、多位数解析、符号处理等多个细节，吃透这道题，能轻松应对同类的表达式求值问题（如 LeetCode 227. 基本计算器 II，支持乘除运算）。