普通视图

昨天以前首页

从输入URL到页面显示的完整技术流程

作者 Wect

2026年2月22日 13:53

一、引言

在Web应用场景中，用户输入统一资源定位符（URL）到页面最终渲染显示，是一个涉及浏览器、网络协议、服务器交互的复杂技术链路。该链路涵盖URL解析、DNS域名解析、TCP/TLS连接建立、HTTP请求响应、浏览器渲染等多个核心环节，各环节紧密衔接、协同工作，直接决定了页面加载速度与交互体验。本文将从技术原理出发，系统拆解整个流程的核心机制，梳理各环节的关键技术要点，为相关技术研究、开发实践及面试备考提供严谨、客观的参考依据。

二、主体分析：从URL到页面显示的完整流程

（一）URL解析：资源定位的前置准备

URL作为Web资源的唯一标识，浏览器接收用户输入的字符串后，首先需完成URL的解析与补全，确保能够准确定位目标服务器及对应资源。该过程的核心是校验URL合法性，并拆解其核心组成部分。

浏览器会对输入字符串进行格式校验，判断其是否符合URL标准规范。若输入字符串不完整（如仅输入“www.example.com”），浏览器将自动补全协议、默认端口等必要字段，补全后为“www.example.com/”；其中，HTTPS协…

一个完整的URL结构可拆解为六个核心部分，以“www.example.com:443/path?query=…

协议（scheme）：即https，用于定义浏览器与服务器之间的通信规则，常用协议还包括HTTP、FTP等；
域名（host）：即www.example.com，作为服务器的别名，用于简化用户记忆，需通过DNS解析转换为网络可识别的IP地址；
端口（port）：即443，用于区分服务器上的不同服务，默认端口可省略；
路径（path）：即/path，用于指定服务器上具体资源的存储位置，如“/index.html”对应服务器根目录下的首页文件；
查询参数（query）：即?query=1，用于向服务器传递额外请求参数，多个参数以“&”分隔；
锚点（hash）：即#hash，用于定位页面内的具体位置，仅在浏览器本地生效，不会随HTTP请求发送至服务器。

（二）DNS查询：域名与IP的映射转换

网络通信的本质是IP地址之间的交互，服务器与客户端仅能通过IP地址识别彼此。由于IP地址具有复杂性、难记忆的特点，DNS（域名系统）应运而生，其核心功能是实现域名到IP地址的映射转换，相当于网络世界的“通讯录”。

DNS查询遵循“从近到远、从本地到远程”的顺序，优先查询本地缓存以提升查询效率，缓存未命中时再发起远程查询，完整流程如下：

浏览器DNS缓存：浏览器会缓存近期查询过的域名-IP映射关系，缓存有效期较短（通常为几分钟至几小时），查询时优先匹配，命中则直接获取IP地址；
操作系统DNS缓存：若浏览器缓存未命中，将查询操作系统自带的DNS缓存，如Windows系统的hosts缓存、Mac系统的DNS缓存；
本地hosts文件：操作系统缓存未命中时，读取本地hosts文件，该文件可手动配置域名与IP的映射关系，常用于开发测试场景（如配置“127.0.0.1 localhost”）；
本地DNS服务器：以上缓存均未命中时，向本地DNS服务器（通常由网络运营商提供，如电信、联通DNS服务器）发送查询请求，运营商服务器会缓存常用域名的解析结果；
递归与迭代查询：若本地DNS服务器未缓存目标域名解析结果，将通过“递归+迭代”的方式逐层查询，依次向根域名服务器、顶级域名服务器（如.com、.cn服务器）、目标域名服务器发起请求，最终获取目标IP地址，并返回给浏览器同时进行缓存。

DNS查询的核心机制可分为递归查询与迭代查询：客户端与本地DNS服务器之间采用递归查询，即客户端仅需等待最终解析结果，由本地DNS服务器完成全程查询操作；DNS服务器之间采用迭代查询，即各服务器仅告知后续查询的目标服务器地址，不负责全程查询，直至获取最终IP地址。

（三）TCP/TLS握手：可靠安全连接的建立

获取目标服务器IP地址后，浏览器需与服务器建立通信连接，其中HTTP协议基于TCP协议实现可靠数据传输，HTTPS协议则在TCP协议之上增加TLS协议，实现数据加密与身份校验，保障通信安全。

1. TCP三次握手：可靠连接的建立

TCP（传输控制协议）的核心特性是可靠传输，三次握手是建立TCP连接的必要流程，其目的是确认双方的发送能力与接收能力均正常，避免历史延迟请求引发的错误连接，保障连接可靠性。三次握手流程如下：

客户端向服务器发送SYN报文，发起连接请求，告知服务器客户端准备建立连接；
服务器接收SYN报文后，返回SYN+ACK报文，确认接收客户端请求，同时向客户端发起连接请求；
客户端接收SYN+ACK报文后，返回ACK报文，确认接收服务器请求，完成三次握手。

三次握手的合理性可通过对比分析验证：若仅采用两次握手，服务器发送SYN+ACK报文后即确认连接建立，但无法确认客户端是否能接收自身报文，若客户端ACK报文丢失，服务器将持续等待，造成资源浪费；若采用四次握手，将在三次握手基础上增加额外确认步骤，不会提升连接可靠性，反而会增加通信延迟，降低传输效率。

2. TLS握手：安全通信的保障

HTTPS协议是HTTP协议与TLS（传输层安全协议）的结合，相比HTTP协议的明文传输，HTTPS通过TLS握手实现身份校验与数据加密，避免数据被窃取、篡改。TLS握手的核心操作如下：

加密算法协商：客户端与服务器协商一致，确定双方均支持的加密算法（如AES对称加密、RSA非对称加密），确保后续数据加密与解密可正常执行；
服务器证书校验：服务器向客户端发送由权威CA机构颁发的SSL证书，客户端校验证书的合法性（包括证书有效期、是否被篡改等），确认服务器身份的真实性，避免中间人劫持；
对称密钥生成：证书校验通过后，客户端与服务器协商生成对称密钥，后续所有HTTP请求与响应数据均通过该密钥加密/解密，兼顾安全性与传输效率；
握手完成确认：双方确认TLS握手完成，后续通信数据将采用协商好的对称密钥进行加密传输，保障通信安全。

与HTTP协议相比，HTTPS协议的核心差异的是增加了TLS握手环节，通过身份校验与数据加密，解决了HTTP协议明文传输的安全隐患。

（四）HTTP请求与响应：资源的传输交互

TCP（或TLS+TCP）连接建立完成后，浏览器向服务器发起HTTP请求，服务器接收请求并处理后，返回HTTP响应，完成Web资源的传输交互，这是整个链路中资源传递的核心环节。

1. HTTP请求报文

HTTP请求报文由请求行、请求头、空行、请求体四部分组成，简化示例如下：

GET /index.html HTTP/1.1  # 请求行：请求方法 + 资源路径 + HTTP版本
Host: www.example.com     # 请求头：传递额外请求信息
Cookie: username=test
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) Chrome/120.0.0.0
                          # 空行：分隔请求头与请求体
# 请求体：GET请求通常为空，POST请求用于传递表单等参数

常用HTTP请求方法包括：GET（用于获取Web资源，如打开页面）、POST（用于提交数据，如登录、表单提交）、PUT（用于修改资源）、DELETE（用于删除资源），不同请求方法对应不同的服务器处理逻辑。

2. HTTP响应报文

HTTP响应报文与请求报文对应，由响应行、响应头、空行、响应体四部分组成，简化示例如下：

HTTP/1.1 200 OK          # 响应行：HTTP版本 + 状态码 + 状态描述
Content-Type: text/html  # 响应头：传递资源相关信息
Content-Length: 1024
Cache-Control: max-age=3600

<html><head><title>示例页面</title></head><body>...</body></html>  # 响应体：核心Web资源

3. 常见HTTP状态码

HTTP状态码用于告知浏览器请求处理结果，分为5大类，核心常用状态码如下：

200 OK：请求处理成功，服务器正常返回目标资源，是最常见的状态码；
301 永久重定向：请求的资源已永久迁移至新地址，浏览器将自动跳转至新地址；
302 临时重定向：请求的资源临时迁移至新地址，跳转行为仅在本次请求有效；
304 Not Modified：目标资源未发生修改，浏览器可直接使用本地缓存，提升加载速度；
404 Not Found：请求的资源不存在，通常由URL输入错误、资源被删除导致；
500 Internal Server Error：服务器内部出现错误（如代码报错、服务器宕机），与客户端请求无关。

（五）浏览器解析：渲染前置的结构构建

浏览器接收服务器返回的HTTP响应后，若响应体为HTML资源，不会直接渲染显示，需先完成HTML、CSS、JS的解析，构建DOM树、CSSOM树及渲染树（Render Tree），为后续页面渲染提供基础结构，这是页面渲染的前置环节。

1. HTML解析与DOM树构建

浏览器对HTML的解析遵循自上而下、逐行解析的原则，将HTML文档中的标签、文本、属性等，转换为浏览器可识别的文档对象模型树（DOM Tree）。DOM Tree的根节点为标签，各子节点对应HTML中的各类元素，层级结构与HTML文档保持一致。

该解析过程的核心特点是：遇到未添加defer/async属性的<script>标签时，会阻塞HTML解析。原因在于JavaScript代码可能对DOM进行操作（如修改、删除DOM节点），浏览器需先执行完JavaScript代码，再继续解析后续HTML内容，避免解析结果与JS操作冲突。

2. CSS解析与CSSOM树构建

CSS解析与HTML解析可并行执行，不依赖HTML解析顺序，但会阻塞页面渲染。浏览器将页面中所有CSS样式（内联样式、内部样式、外部样式）解析后，构建CSS对象模型树（CSSOM Tree），该树明确了每个DOM节点对应的样式规则（如字体、颜色、尺寸等）。

若JavaScript代码中存在获取元素样式的操作（如getComputedStyle()），浏览器将先完成CSS解析与CSSOM树构建，再执行对应的JavaScript代码，确保JS获取的样式信息准确无误。

3. 渲染树（Render Tree）构建

DOM树与CSSOM树构建完成后，浏览器将两者合并，生成渲染树（Render Tree）。渲染树的核心特点是仅包含页面可见节点，不可见节点（如display: none属性的元素）不会被纳入渲染树，避免无效渲染；而visibility: hidden属性的元素，虽视觉上隐藏但仍占据页面布局空间，会被纳入渲染树。渲染树是后续页面布局、绘制的核心依据。

（六）页面渲染：视觉呈现的核心流程

渲染树构建完成后，浏览器通过布局（Layout）、绘制（Paint）、合成（Composite）三个依次执行的核心步骤，将Web资源渲染显示在屏幕上，形成用户最终看到的页面，该流程直接决定页面的视觉呈现效果与加载效率。

1. 布局（Layout）：元素位置与尺寸的计算

布局又称回流或重排，其核心作用是根据渲染树，计算每个可见元素的位置与尺寸，包括元素的宽度、高度、left/top坐标等，明确每个元素在页面中的具体布局位置。

触发布局的常见场景包括：元素尺寸或位置修改（如修改width、height、margin属性）、页面窗口大小调整、DOM节点的添加或删除等，布局操作会触发后续绘制与合成步骤，对页面加载效率有一定影响。

2. 绘制（Paint）：元素视觉样式的绘制

绘制又称重绘，其核心作用是根据布局计算的结果，在浏览器的绘制层上，为每个元素绘制视觉样式，包括颜色、边框、背景、文字、图片等，将元素的视觉属性呈现出来。

触发绘制的常见场景包括：元素视觉样式修改（如修改color、background-color、border-color属性），但元素尺寸与位置未发生变化，此时仅触发绘制与合成步骤，无需重新执行布局，效率高于布局操作。

3. 合成（Composite）：分层渲染与屏幕显示

合成又称分层合成，其核心作用是将绘制完成的多个绘制层，通过GPU（图形处理器）进行分层合成，将所有绘制层整合为一个完整的页面，最终渲染显示在屏幕上。

GPU分层合成的优势在于效率高，不同绘制层相互独立，修改某一层的元素时，无需重新绘制整个页面，仅需重新合成该层即可，可显著提升页面交互的流畅度。例如，修改元素的transform属性（GPU加速属性）时，仅触发合成步骤，无需执行布局与绘制，效率最优。

（七）完整流程汇总

从输入URL到页面显示的完整技术流程可总结为：用户输入URL后，浏览器先完成URL解析与补全，明确通信协议、域名、端口等核心信息；通过DNS解析系统，将域名转换为对应的IP地址；与服务器建立TCP连接，HTTPS协议额外执行TLS握手确保通信安全；连接建立后，浏览器发送HTTP请求，服务器处理后返回HTTP响应；浏览器解析HTML构建DOM树、解析CSS构建CSSOM树，合并生成渲染树；最后通过布局、绘制、合成三个步骤，将页面渲染显示在屏幕上，完成整个流程。

（八）追问常见

1. DNS 是递归还是迭代？

DNS查询的核心机制分为递归查询与迭代查询，二者应用场景不同、职责明确：客户端与本地DNS服务器之间采用递归查询，即客户端无需参与中间查询过程，仅需等待本地DNS服务器返回最终的IP解析结果，全程由本地DNS服务器完成逐层查询操作；DNS服务器之间（包括本地DNS服务器与根域名服务器、顶级域名服务器、目标域名服务器之间）采用迭代查询，即各服务器仅向发起查询的服务器告知后续查询的目标服务器地址，不负责全程查询，直至某一服务器返回最终IP地址，查询流程终止。

2. HTTPS 比 HTTP 多了哪一步？

与HTTP协议相比，HTTPS协议的核心差异是增加了TLS（传输层安全协议）握手环节。HTTP协议基于TCP协议进行明文传输，数据易被窃取、篡改，无身份校验机制；而HTTPS协议在TCP三次握手建立连接后，会额外执行TLS握手流程，完成加密算法协商、服务器证书校验、对称密钥生成等操作，实现通信数据的加密传输与服务器身份的真实性校验，从而解决HTTP协议明文传输的安全隐患，保障网络通信的安全性。

3. TCP 三次握手为什么是三次？

TCP三次握手的核心目的是确认通信双方的发送能力与接收能力均正常，同时避免历史延迟请求引发的错误连接，保障TCP连接的可靠性，其次数设定具有明确的合理性，既不能减少为两次，也无需增加至四次。若仅采用两次握手，服务器发送SYN+ACK报文后即确认连接建立，但无法确认客户端是否能接收自身发送的报文，若客户端的ACK报文丢失，服务器会持续等待连接，造成服务器资源浪费；若采用四次握手，会在三次握手的基础上增加额外的确认步骤，该步骤无法提升连接的可靠性，反而会增加网络通信延迟，降低数据传输效率，因此三次握手是兼顾可靠性与效率的最优选择。

三、结论

从输入URL到页面显示的过程，是浏览器、网络协议与服务器协同工作的集中体现，涵盖URL解析、DNS查询、TCP/TLS连接、HTTP请求响应、浏览器解析与渲染六大核心环节，各环节环环相扣、缺一不可。其中，URL解析与DNS查询为资源定位提供基础，TCP/TLS连接保障通信的可靠与安全，HTTP请求响应实现资源传输，浏览器解析与渲染完成页面视觉呈现。

深入理解该技术流程，不仅能够帮助开发者优化页面加载速度、提升用户体验，解决开发中的各类网络与渲染相关问题，同时也是计算机网络、前端开发等领域面试的核心考点。

掘金前端
LeetCode 105. 从前序与中序遍历序列构造二叉树：题解与思路解析Wect
2026年2月19日 19:53

LeetCode 105. 从前序与中序遍历序列构造二叉树：题解与思路解析

掘金前端

作者 Wect

2026年2月19日 19:53

在二叉树的算法题型中，“根据遍历序列构造二叉树”是经典考点，而 LeetCode 105 题——从前序与中序遍历序列构造二叉树，更是这一考点的核心代表。这道题不仅能考察我们对二叉树遍历规则的理解，还能检验递归思维和哈希表优化的应用，今天就来一步步拆解这道题，从思路到代码，吃透每一个细节。

一、题目回顾

题目给出两个整数数组preorder 和 inorder，其中 preorder 是二叉树的先序遍历序列，inorder 是同一棵二叉树的中序遍历序列，要求我们构造这棵二叉树并返回其根节点。

补充基础：二叉树遍历规则

先序遍历（preorder）：根节点 → 左子树 → 右子树（根在前，左右在后）；
中序遍历（inorder）：左子树 → 根节点 → 右子树（根在中间，左右分居两侧）。

核心关键：先序遍历的第一个元素一定是二叉树的根节点；而中序遍历中，根节点左侧的所有元素是左子树的中序序列，右侧的所有元素是右子树的中序序列。利用这两个特性，我们就能递归地构造出整个二叉树。

二、解题思路（核心逻辑）

这道题的解题核心是「递归分治」，配合哈希表优化查找效率，具体思路可以分为 4 步，我们结合例子来理解（假设 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]）：

步骤1：确定根节点

根据先序遍历规则，preorder 的第一个元素 preorder[0] 就是整个二叉树的根节点（例子中根节点是 3）。

步骤2：划分左右子树的中序序列

在中序序列 inorder 中找到根节点的索引（例子中 3 的索引是 1）：

根节点左侧的元素（[9]）：左子树的中序序列；
根节点右侧的元素（[15,20,7]）：右子树的中序序列。

步骤3：划分左右子树的先序序列

左右子树的节点数量，在中序序列和先序序列中是一致的：

左子树的节点数 = 根节点在中序的索引 - 中序序列的起始索引（例子中 1 - 0 = 1，左子树有 1 个节点）；
因此，先序序列中，根节点之后的「左子树节点数」个元素（[9]）是左子树的先序序列；
剩下的元素（[20,15,7]）是右子树的先序序列。

步骤4：递归构造左右子树

对左子树和右子树，重复上述 3 个步骤：找到子树的根节点、划分左右子序列，直到序列为空（递归终止条件），最终拼接出整个二叉树。

优化点：哈希表加速查找

如果每次在中序序列中查找根节点都用遍历的方式，时间复杂度会达到 O(n²)（n 是节点总数）。我们可以提前用哈希表（Map）存储中序序列中「元素 → 索引」的映射，这样每次查找根节点的索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

先给出 TreeNode 类的定义（题目已提供，此处复用并补充注释），再实现核心的 buildTree 函数，每一步代码都附上详细注释，方便理解：

// 二叉树节点类定义
class TreeNode {
  val: number
  left: TreeNode | null  // 左子节点，默认为null
  right: TreeNode | null // 右子节点，默认为null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val) // 节点值，默认0
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 1. 构建中序序列的哈希映射，key是节点值，value是对应索引
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  /**
   * 递归辅助函数：构造当前范围内的二叉树
   * @param preorderStart 先序序列当前范围的起始索引
   * @param preorderEnd 先序序列当前范围的结束索引
   * @param inorderStart 中序序列当前范围的起始索引
   * @param inorderEnd 中序序列当前范围的结束索引
   * @returns 当前范围的二叉树根节点
   */
  const helper = (
    preorderStart: number, 
    preorderEnd: number, 
    inorderStart: number, 
    inorderEnd: number
  ): TreeNode | null => {

    // 递归终止条件：当前范围无节点（起始索引>结束索引），返回null
    if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
      return null;
    }

    // 2. 确定当前范围的根节点（先序序列的第一个元素）
    const rootVal = preorder[preorderStart];
    const root = new TreeNode(rootVal); // 创建根节点

    // 3. 找到根节点在中序序列中的索引，用于划分左右子树
    const inorderIndex = map.get(rootVal)!; // ！表示非null断言（确保能找到索引）
    const leftSize = inorderIndex - inorderStart; // 左子树的节点数

    // 4. 递归构造左子树
    // 左子树先序范围：preorderStart+1 ~ preorderStart+leftSize（根节点后leftSize个元素）
    // 左子树中序范围：inorderStart ~ inorderIndex-1（根节点左侧元素）
    root.left = helper(
      preorderStart + 1, 
      preorderStart + leftSize, 
      inorderStart, 
      inorderIndex - 1
    );

    // 5. 递归构造右子树
    // 右子树先序范围：preorderStart+leftSize+1 ~ preorderEnd（左子树之后的剩余元素）
    // 右子树中序范围：inorderIndex+1 ~ inorderEnd（根节点右侧元素）
    root.right = helper(
      preorderStart + leftSize + 1, 
      preorderEnd, 
      inorderIndex + 1, 
      inorderEnd
    );

    return root; // 返回当前范围的根节点
  }

  // 初始调用递归函数，范围是整个先序和中序序列
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

四、代码关键细节解析

1. 递归终止条件

当 preorderStart > preorderEnd 或 inorderStart > inorderEnd 时，说明当前范围内没有节点，返回 null（比如叶子节点的左右子节点，就会触发这个条件）。

2. 左子树节点数的计算

leftSize = inorderIndex - inorderStart，这个计算是划分先序序列的关键——因为先序序列中，根节点之后的 leftSize 个元素，必然是左子树的先序序列，剩下的就是右子树的先序序列。

3. 哈希表的非null断言

代码中 map.get(rootVal)! 用到了 TypeScript 的非null断言（!），原因是题目保证了 preorder 和 inorder 是同一棵二叉树的遍历序列，因此根节点的值一定能在中序序列中找到，不会返回 null。

4. 时间和空间复杂度

时间复杂度：O(n)，n 是节点总数。哈希表构建需要 O(n) 时间，递归过程中每个节点被处理一次，每次查找根节点索引是 O(1)；
空间复杂度：O(n)，哈希表存储 n 个元素，递归调用栈的深度最坏情况下是 O(n)（比如斜树），最好情况下是 O(log n)（平衡二叉树）。

五、常见易错点提醒

先序序列的划分错误：容易把右子树的先序起始索引算错，记住是 preorderStart + leftSize + 1（跳过根节点和左子树）；
中序序列的边界错误：左子树的中序结束索引是 inorderIndex - 1，右子树的中序起始索引是 inorderIndex + 1，容易漏写 ±1 导致死循环；
忽略空数组情况：当 preorder 和 inorder 为空时，直接返回 null（递归终止条件会处理，但需注意初始调用时的边界）；
不用哈希表优化：直接遍历中序序列找根节点，会导致时间复杂度飙升，在 n 较大时（比如 10^4 级别）会超时。

六、总结

LeetCode 105 题的核心是「利用遍历序列的特性 + 递归分治 + 哈希表优化」，解题的关键在于抓住“先序定根、中序分左右”的规律，再通过递归逐步构造子树。

这道题不仅能帮我们巩固二叉树的遍历知识，还能锻炼递归思维——递归的本质就是“把大问题拆成小问题，解决小问题后拼接结果”，这里的大问题是“构造整个二叉树”，小问题是“构造左子树”和“构造右子树”。

如果能吃透这道题，再遇到“从中序与后序遍历构造二叉树”（LeetCode 106 题）就会事半功倍，因为思路完全相通，只是根节点的位置和序列划分方式略有不同。

掘金前端
LeetCode 106. 从中序与后序遍历序列构造二叉树：题解+思路拆解Wect
2026年2月19日 20:17

LeetCode 106. 从中序与后序遍历序列构造二叉树：题解+思路拆解

掘金前端

作者 Wect

2026年2月19日 20:17

在二叉树的算法题中，“根据遍历序列构造二叉树”是高频考点，而 LeetCode 106 题（从中序与后序遍历序列构造二叉树）更是经典中的经典。它不仅考察对二叉树遍历规则的理解，还需要运用分治思想拆解问题，新手容易在“区间划分”上栽坑。今天就带大家一步步拆解这道题，从思路分析到代码实现，再到细节避坑，彻底搞懂如何通过两个遍历序列还原二叉树。

一、题目核心认知

先明确题目要求，避免理解偏差：

给定两个整数数组 inorder（中序遍历）和 postorder（后序遍历），二者对应同一棵二叉树；
构造并返回这棵二叉树的根节点；
默认输入有效（无重复元素，且两个数组长度一致，能构成合法二叉树）。

关键前提：二叉树遍历规则回顾

要解决这道题，必须牢记中序和后序遍历的核心特点（这是解题的灵魂）：

中序遍历（左-根-右）：先遍历左子树，再访问根节点，最后遍历右子树；
后序遍历（左-右-根）：先遍历左子树，再遍历右子树，最后访问根节点。

核心突破口：后序遍历的最后一个元素，一定是当前二叉树的根节点；而中序遍历中，根节点左侧的所有元素都是左子树的节点，右侧的所有元素都是右子树的节点。

二、解题思路拆解（分治思想）

既然能通过后序找到根节点，通过中序划分左右子树，那我们就可以用「分治」的思路，把大问题拆成小问题，递归求解：

步骤1：找到根节点

取 postorder 的最后一个元素，作为当前二叉树的根节点（root）。

步骤2：划分中序遍历的左右子树区间

在inorder 中找到根节点的索引（记为 rootIndex），则：

左子树的中序区间：[inorderStart, rootIndex - 1]（根节点左侧所有元素）；
右子树的中序区间：[rootIndex + 1, inorderEnd]（根节点右侧所有元素）。

步骤3：划分后序遍历的左右子树区间

后序遍历的区间长度和中序遍历一致（因为对应同一棵子树），设左子树的节点个数为 leftSize = rootIndex - inorderStart，则：

左子树的后序区间：[postorderStart, postorderStart + leftSize - 1]（左子树节点个数为 leftSize）；
右子树的后序区间：[postorderStart + leftSize, postorderEnd - 1]（去掉最后一个根节点，剩余部分前半为左子树，后半为右子树）。

步骤4：递归构造左右子树

用同样的方法，递归构造左子树和右子树，分别赋值给根节点的 left 和 right 指针。

步骤5：优化索引查询（避免重复遍历）

如果每次在中序数组中找根节点索引都用遍历的方式，时间复杂度会很高（O(n²)）。我们可以提前用一个哈希表（Map），存储中序数组中「元素-索引」的映射，这样每次查询根节点索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

结合上面的思路，我们来实现代码（题目已给出 TreeNode 类，直接复用即可）：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  // 提前存储中序遍历的「元素-索引」映射，优化查询效率
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  // 递归辅助函数：根据区间构造子树
  // inorderStart/inorderEnd：当前子树在中序数组中的区间
  // postorderStart/postorderEnd：当前子树在后序数组中的区间
  const helper = (inorderStart: number, inorderEnd: number, postorderStart: number, postorderEnd: number): TreeNode | null => {
    // 递归终止条件：区间不合法（没有节点），返回null
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
      return null;
    }

    // 1. 找到当前子树的根节点（后序数组的最后一个元素）
    const rootVal = postorder[postorderEnd];
    const root = new TreeNode(rootVal);

    // 2. 找到根节点在中序数组中的索引，划分左右子树区间
    const rootIndex = map.get(rootVal)!; // 题目保证输入有效，非null

    // 3. 计算左子树的节点个数，用于划分后序数组区间
    const leftSize = rootIndex - inorderStart;

    // 4. 递归构造左子树和右子树，赋值给根节点
    // 左子树：中序[start, rootIndex-1]，后序[start, start+leftSize-1]
    root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
    // 右子树：中序[rootIndex+1, end]，后序[start+leftSize, end-1]
    root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

    // 返回当前子树的根节点
    return root;
  }

  // 初始调用：区间为两个数组的完整区间
  return helper(0, inorder.length - 1, 0, postorder.length - 1);
};

四、代码逐行解析（重点+避坑）

很多新手能看懂思路，但写代码时容易在「区间边界」上出错，这里逐行拆解关键部分，帮大家避坑：

1. 哈希表初始化

const map = new Map<number, number>();
inorder.forEach((val, index) => {
  map.set(val, index);
});

作用：提前缓存中序数组的元素和对应索引，后续每次找根节点索引都能直接通过 map.get(rootVal) 获取，避免重复遍历中序数组，降低时间复杂度。

2. 递归辅助函数（helper）

为什么需要辅助函数？因为我们需要通过「区间边界」来划分左右子树，而主函数的参数只有两个数组，无法直接传递区间信息，所以用 helper 函数封装区间参数，实现递归。

3. 递归终止条件

if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
  return null;
}

避坑点：当区间的起始索引大于结束索引时，说明当前区间没有节点，直接返回 null（比如左子树为空或右子树为空的情况）。比如，根节点的左子树如果没有节点，那么 inorderStart 会等于 rootIndex，此时 inorderStart > rootIndex - 1，触发终止条件，返回 null，正好对应 root.left = null。

4. 根节点创建

const rootVal = postorder[postorderEnd];
const root = new TreeNode(rootVal);

核心：后序遍历的最后一个元素就是当前子树的根节点，这是整个解题的突破口，必须牢记。

5. 区间划分（最容易出错的地方）

const leftSize = rootIndex - inorderStart;
// 左子树递归调用
root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
// 右子树递归调用
root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

避坑解析：

leftSize 是左子树的节点个数，由「根节点索引 - 中序起始索引」得到，因为中序左子树区间是 [inorderStart, rootIndex - 1]，长度为 rootIndex - inorderStart；
后序左子树区间的结束索引 = 起始索引 + 左子树节点个数 - 1（因为区间是闭区间，比如起始索引0，个数2，区间是[0,1]）；
后序右子树的起始索引 = 左子树结束索引 + 1，结束索引 = 原后序结束索引 - 1（去掉根节点）；
中序右子树区间直接从 rootIndex + 1 开始，到 inorderEnd 结束即可。

五、复杂度分析

时间复杂度：O(n)，n 是二叉树的节点个数。哈希表初始化遍历一次中序数组（O(n)），每个节点被递归处理一次（O(n)），每次索引查询 O(1)；
空间复杂度：O(n)，哈希表存储 n 个元素（O(n)），递归调用栈的深度最坏情况下为 n（比如二叉树退化为链表），整体空间复杂度 O(n)。

六、总结与拓展

核心总结

这道题的本质是「利用遍历序列的特点找根节点 + 分治思想拆分左右子树」，关键在于两点：

牢记后序最后一个元素是根，中序根节点划分左右子树；
精准划分两个数组的左右子树区间，避免边界出错（建议多动手画示例，标注区间）。

拓展思考

这道题和 LeetCode 105 题（从前序与中序遍历序列构造二叉树）思路高度一致，只是根节点的位置和区间划分略有不同：

105题（前序+中序）：前序的第一个元素是根节点；
106题（后序+中序）：后序的最后一个元素是根节点。

掌握这两道题，就能轻松应对「遍历序列构造二叉树」的所有同类题型。

LeetCode 100. 相同的树：两种解法（递归+迭代）详解

掘金前端

作者 Wect

2026年2月17日 20:50

LeetCode简单难度的经典二叉树题目——100. 相同的树，这道题虽然难度不高，但非常适合入门二叉树的遍历思想，尤其是递归和迭代两种核心思路的对比练习，新手朋友可以重点看看，老手也可以快速回顾巩固一下。

先简单梳理一下题目要求，避免踩坑：给两棵二叉树的根节点p和q，判断这两棵树是否“相同”。这里的相同有两个核心条件，缺一不可：结构上完全一致，并且对应位置的节点值完全相等。

举个直观的例子：如果p是一棵只有根节点（值为1）的树，q也是只有根节点（值为1），那它们是相同的；但如果p的根节点是1、左孩子是2，q的根节点是1、右孩子是2，哪怕节点值都一样，结构不同，也不算相同。

一、题目前置准备

题目已经给出了二叉树节点的定义，用TypeScript实现的，这里再贴一遍，方便大家对照代码理解（注释已补充，新手可重点看构造函数的逻辑）：

class TreeNode {
  val: number; // 节点值
  left: TreeNode | null; // 左孩子，可能为null（没有左孩子）
  right: TreeNode | null; // 右孩子，可能为null（没有右孩子）
  // 构造函数：初始化节点，val默认0，左右孩子默认null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val); // 节点值为空时，默认设为0
    this.left = (left === undefined ? null : left); // 左孩子为空时，默认设为null
    this.right = (right === undefined ? null : right); // 右孩子为空时，默认设为null
  }
}

二、解法一：递归解法

1. 递归思路分析

递归的核心思想是“分而治之”，把判断两棵大树是否相同，拆解成判断无数个“小问题”——判断当前两个节点是否相同，以及它们的左孩子、右孩子是否分别相同。

递归的终止条件（也是边界情况）很关键，分三步判断，逻辑层层递进：

如果p和q都为null（两个节点都不存在）：说明这两个位置的节点是相同的，返回true；
如果p和q中一个为null、另一个不为null（一个节点存在，一个不存在）：说明结构不同，返回false；
如果p和q都不为null，但它们的val不相等（节点值不同）：说明节点不相同，返回false；

如果以上三种情况都不满足，说明当前两个节点是相同的，接下来就递归判断它们的左孩子（p.left和q.left）和右孩子（p.right和q.right），只有左右孩子都相同，整棵树才相同（用&&连接两个递归结果）。

2. 递归代码实现

// 递归解法：isSameTree_1
function isSameTree_1(p: TreeNode | null, q: TreeNode | null): boolean {
  // 边界情况1：两个节点都为空，相同
  if (p === null && q === null) {
    return true;
  }
  // 边界情况2：一个为空，一个不为空，结构不同，不相同
  if (p === null || q === null) {
    return false;
  }
  // 边界情况3：两个节点都不为空，但值不同，不相同
  if (p.val !== q.val) {
    return false;
  }
  // 递归：当前节点相同，判断左孩子和右孩子是否都相同
  return isSameTree_1(p.left, q.left) && isSameTree_1(p.right, q.right);
};

3. 递归解法总结

优点：代码极度简洁，逻辑清晰，完全贴合二叉树的递归特性，容易理解和编写，新手友好；

缺点：递归依赖调用栈，如果二叉树深度极深（比如链式二叉树），可能会出现栈溢出的情况（但LeetCode的测试用例一般不会卡这种极端情况，日常刷题完全够用）；

时间复杂度：O(n)，n是两棵树中节点数较少的那一个，每个节点只会被访问一次；

空间复杂度：O(h)，h是树的高度，最坏情况下（链式树）h=n，最好情况下（平衡树）h=logn。

三、解法二：迭代解法（用栈模拟递归，避免栈溢出）

1. 迭代思路分析

迭代解法的核心是“用栈模拟递归的调用过程”，通过手动维护一个栈，把需要判断的节点对（p的节点和q的对应节点）压入栈中，然后循环弹出节点对进行判断，本质上和递归的逻辑是一致的，只是实现方式不同。

具体步骤：

先判断两棵树的根节点是否都为空（和递归边界1一致），如果是，直接返回true；
如果根节点一个为空、一个不为空（和递归边界2一致），直接返回false；
初始化一个栈，把根节点对（p和q）压入栈中（注意压入顺序，后续弹出时要对应）；
循环：只要栈不为空，就弹出两个节点（pNode和qNode），进行判断；
判断弹出的两个节点：如果都为空，跳过（继续判断下一组节点）；如果一个为空一个不为空，返回false；如果值不相等，返回false；
如果当前节点对相同，就把它们的左孩子对、右孩子对依次压入栈中（注意压入顺序，先压右孩子，再压左孩子，因为栈是“后进先出”，和递归的顺序保持一致）；
循环结束后，说明所有节点对都判断完毕，没有发现不相同的情况，返回true。

这里有个小细节：压入栈的顺序是“p.left、q.left、p.right、q.right”，弹出的时候会先弹出p.right和q.right，再弹出p.left和q.left，和递归时“先判断左孩子，再判断右孩子”的顺序是一致的，不影响结果，但要注意保持对应关系，不能压混。

2. 迭代代码实现

// 迭代解法：isSameTree_2（栈模拟递归）
function isSameTree_2(p: TreeNode | null, q: TreeNode | null): boolean {
  // 先处理根节点的边界情况（和递归一致）
  if (p === null && q === null) {
    return true;
  }
  if (p === null || q === null) {
    return false;
  }
  // 初始化栈，压入根节点对（p和q）
  let stack: (TreeNode | null)[] = [];
  stack.push(p);
  stack.push(q);
  
  // 循环：栈不为空时，持续判断节点对
  while (stack.length > 0) {
    // 弹出两个节点，注意栈是后进先出，所以先弹出q，再弹出p（对应压入顺序）
    let qNode: TreeNode | null = stack.pop() ?? null;
    let pNode: TreeNode | null = stack.pop() ?? null;
    
    // 两个节点都为空，跳过（继续判断下一组）
    if (pNode === null && qNode === null) {
      continue;
    }
    // 一个为空一个不为空，结构不同，返回false
    if (pNode === null || qNode === null) {
      return false;
    }
    // 节点值不同，返回false
    if (pNode.val !== qNode.val) {
      return false;
    }
    
    // 当前节点对相同，压入它们的左孩子对和右孩子对（保持对应关系）
    stack.push(pNode.left);
    stack.push(qNode.left);
    stack.push(pNode.right);
    stack.push(qNode.right);
  }
  
  // 所有节点对都判断完毕，没有不相同的情况，返回true
  return true;
}

3. 迭代解法总结

优点：不依赖递归调用栈，避免了极端情况下的栈溢出问题，稳定性更好；

缺点：代码比递归稍长，需要手动维护栈和循环逻辑，对新手来说稍微复杂一点；

时间复杂度：O(n)，和递归一致，每个节点只会被压入栈、弹出栈各一次，访问一次；

空间复杂度：O(n)，最坏情况下（平衡树），栈中会存储n/2个节点对，空间复杂度为O(n)；最好情况下（链式树），栈中最多存储2个节点对，空间复杂度为O(1)。

四、两种解法对比 & 刷题建议

解法类型	优点	缺点	适用场景
递归	代码简洁、逻辑清晰、易编写	极端情况下可能栈溢出	日常刷题、二叉树深度不深的场景
迭代（栈）	无栈溢出问题、稳定性好	代码稍长、需维护栈逻辑	二叉树深度极深、生产环境场景

刷题建议：新手先掌握递归解法，因为它最贴合二叉树的特性，后续做二叉树的遍历、对称树、翻转树等题目时，思路可以无缝迁移；掌握递归后，再理解迭代解法，重点体会“栈模拟递归”的思想，这是二叉树迭代题目的核心套路。

五、常见踩坑点提醒

踩坑点1：忽略“结构不同”的情况，只判断节点值。比如p有左孩子、q没有左孩子，但其他节点值都相同，此时会误判为相同；
踩坑点2：递归时忘记写终止条件，导致无限递归，栈溢出；
踩坑点3：迭代时压入栈的节点对顺序混乱，导致弹出时判断的不是“对应节点”（比如把p.left和q.right压在一起）；
踩坑点4：处理节点为null时不严谨，比如用p.val === q.val时，没有先判断p和q是否为null，导致空指针错误（代码中已规避此问题）。

六、总结

LeetCode 100. 相同的树，本质上是二叉树“同步遍历”的入门练习，核心是判断“结构+节点值”是否双匹配。递归解法胜在简洁，迭代解法胜在稳定，两种解法的逻辑完全一致，只是实现方式不同。

刷这道题的重点不在于“写出代码”，而在于理解“如何同步判断两棵树的对应节点”，这个思路后续会用到很多类似题目中（比如101. 对称二叉树，只是判断的是“自身的左孩子和右孩子”，逻辑高度相似）。

LeetCode 104. 二叉树的最大深度：解题思路+代码解析

掘金前端

作者 Wect

2026年2月17日 18:29

LeetCode基础题第104题「二叉树的最大深度」，这道题是二叉树遍历的经典入门题，核心考察对二叉树层次遍历（BFS）的理解和应用，适合新手入门练手。今天就来详细拆解这道题，从题目理解到代码实现，再到细节优化，一步步讲清楚，看完就能轻松掌握。

一、题目解读

题目描述

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

简单来说，就是要找到二叉树“最深”的那一层，统计从根到这一层的所有节点个数。举个例子：

如果二叉树只有根节点，没有左右子节点，最大深度就是1；
如果根节点有左子节点，左子节点又有一个子节点，那么最大深度就是3；
如果二叉树是空树（root为null），最大深度就是0。

核心考点

这道题的核心是「二叉树的遍历」，常见的解法有两种：

层次遍历（BFS，广度优先搜索）：按层遍历二叉树，每遍历完一层，深度加1，最终的深度就是最大深度（本文重点讲解这种解法，对应给出的代码）；
深度优先搜索（DFS）：递归遍历左右子树，取左右子树的最大深度，再加上当前根节点的深度1，即为整个树的最大深度（后续会补充备选代码）。

二、代码解析（TypeScript）

先贴出完整代码（已优化，解决原代码潜在问题），再逐行拆解思路，新手也能看懂～

/**
 * Definition for a binary tree node.
 * 二叉树节点的定义（题目已给出，无需修改）
 */
class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

/**
 * 计算二叉树最大深度（层次遍历/BFS解法）
 * @param root 二叉树根节点
 * @returns 二叉树的最大深度
 */
function maxDepth(root: TreeNode | null): number {
  // 边界处理：空树直接返回深度0（避免后续无效循环）
  if (root === null) {
    return 0;
  }

  let depth = 0; // 记录当前深度，初始化为0
  // 用数组模拟队列，存储当前层的所有节点（初始存入根节点）
  const queue: TreeNode[] = [root];

  // 队列不为空，说明还有节点未遍历，继续循环
  while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点个数
    // 遍历当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      // 取出当前层的节点（优化：用pop+unshift替代shift，提升性能）
      const node = queue.pop()!;
      
      // 若当前节点有右子节点，存入队列（先存右，再存左，保证遍历顺序）
      if (node.right) {
        queue.unshift(node.right);
      }
      // 若当前节点有左子节点，存入队列
      if (node.left) {
        queue.unshift(node.left);
      }
    }
    // 可选：打印队列，观察每一层遍历后的节点变化（调试用）
    
    
    // 当前层遍历完毕，深度加1
    depth++;
  }

  return depth;
}

逐行拆解思路

1. 边界处理（关键！）

if (root === null) { return 0; }

这一步是很多新手容易忽略的点：如果二叉树是空树（root为null），没有任何节点，最大深度自然是0。如果不做这个判断，后续队列会存入null，导致循环多执行一次，最终返回错误的深度1。

2. 初始化变量

let depth = 0;：用于记录二叉树的深度，初始值为0（因为还未开始遍历任何一层）；
const queue: TreeNode[] = [root];：用数组模拟队列（队列是BFS的核心数据结构），初始时将根节点存入队列，代表从根节点开始遍历。

3. 层次遍历核心循环

while (queue.length > 0) { ... }：队列不为空，说明还有节点未遍历，循环继续。每一次循环，都代表遍历完「一层」节点。

4. 遍历当前层节点

const levelSize = queue.length;：获取当前层的节点个数，这个值是固定的（因为后续队列会存入下一层的节点，不能直接用queue.length判断当前层节点数）。

for (let i = 0; i < levelSize; i++) { ... }：循环遍历当前层的每一个节点，把每个节点的左右子节点（如果有的话）存入队列，为下一层遍历做准备。

5. 节点取出与子节点入队（性能优化点）

原代码中如果用queue.shift()取出节点，会有性能问题——因为数组的shift()方法是O(n)时间复杂度（需要将数组中所有元素向前移动一位），当二叉树节点较多时，效率会很低。

优化方案：用queue.pop()（O(1)时间复杂度）取出队列尾部的节点，同时调整子节点入队顺序（先存右子节点，再存左子节点），保证遍历顺序和shift()一致，既提升性能，又不影响结果。

这里的!是非空断言，因为我们已经通过边界处理和循环条件，确保队列中的节点一定是TreeNode类型（不会为null），所以可以安全使用非空断言。

6. 深度递增

depth++;：每遍历完一层，说明二叉树的深度增加了1，所以深度加1。当循环结束时，depth就是二叉树的最大深度。

三、代码优化说明

对比LeetCode题目给出的初始模板，这段代码做了3个关键优化，兼顾性能和正确性：

新增边界处理：解决空树返回错误深度的问题，让代码更健壮；
性能优化：用pop() + unshift()替代shift()，将节点取出操作的时间复杂度从O(n)降至O(1)，适合处理节点较多的二叉树；

可读性优化：添加详细注释，变量命名语义化（如levelSize代表当前层节点数），方便新手理解每一步的执行过程。

四、备选解法（DFS递归版）

除了上述层次遍历（BFS）解法，这道题还可以用深度优先搜索（DFS）的递归写法，代码更简洁，适合树深度不大的场景（避免递归栈溢出），新手也可以了解一下：

function maxDepthRecursive(root: TreeNode | null): number {
  // 空树返回0
  if (root === null) {
    return 0;
  }
  // 递归计算左右子树的最大深度，当前深度 = 左右子树最大深度 + 1（当前节点）
  return Math.max(maxDepthRecursive(root.left), maxDepthRecursive(root.right)) + 1;
}

递归解法的核心思路：二叉树的最大深度 = 左子树最大深度和右子树最大深度的最大值 + 1（当前根节点），本质是遍历到最底层的叶子节点，再回溯计算深度。

五、总结

LeetCode 104题是二叉树遍历的入门题，难度简单，但能很好地巩固BFS和DFS的基础思路。本文讲解的层次遍历（BFS）解法，适合所有场景（包括极深的二叉树，避免递归栈溢出），优化后的代码兼顾性能和可读性，新手可以重点掌握。

解题关键记住两点：

边界处理：空树直接返回0，避免错误；
层次遍历核心：用队列存储每一层的节点，每遍历完一层，深度加1。

LeetCode 25. K个一组翻转链表：两种解法详解+避坑指南

掘金前端

作者 Wect

2026年2月14日 15:04

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 为例）

初始状态：dummy(0)->1->2->3->4，preGroup=dummy，prev=dummy，curr=1，count=0；
遍历curr=1：count≠2，翻转1（1.next=prev=dummy），prev=1，curr=2，count=1；
遍历curr=2：count≠2，翻转2（2.next=prev=1），prev=2，curr=3，count=2；
凑够k=2个节点：调整组间连接——preGroup.next=prev=2（dummy->2），原组头lastNode=1，1.next=curr=3（2->1->3）；更新preGroup=1，prev=1，count=0；
继续遍历curr=3：重复步骤2-3，翻转3、4，凑够k=2个节点，调整连接（1->4，3.next=null）；
循环结束，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 为例）

初始状态：dummy(0)->1->2->3->4，preGroup=dummy；
找第一组边界：groupTail从preGroup开始移动2次，找到groupTail=2（确认够k个节点）；记录groupHead=1，nextGroupHead=3；
单独翻转当前组（1->2）：prev初始化为nextGroupHead=3，curr=groupHead=1；循环翻转，直到curr=nextGroupHead，翻转后变成2->1；
连接组间：preGroup.next=groupTail=2（dummy->2），preGroup更新为groupHead=1（下一组的前置节点）；
找第二组边界：groupTail从preGroup=1移动2次，找到groupTail=4；记录groupHead=3，nextGroupHead=null；
单独翻转当前组（3->4），连接组间；
下一次找组边界：移动不足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 ：题解与思路解析

掘金前端

作者 Wect

2026年2月13日 21:19

反转链表是链表类题目中的基础题型，但 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]

二、核心难点分析

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

如何精准定位到 left 节点的前驱节点（记为 leftPreNode）和 right 节点的后继节点（记为 temp）？这两个节点是连接「未反转部分」和「反转部分」的关键，一旦处理不好就会出现链表断裂。
反转区间内的节点时，如何保证指针迭代不混乱？反转过程中 prev、curr 指针的移动的顺序，直接影响反转是否正确。
边界场景的处理：比如 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 题的核心是「局部反转 + 边界连接」，解题的关键在于：

用虚拟头节点简化表头反转的特殊处理；
精准定位 left 的前驱、反转区间的首尾节点；
反转过程中注意指针的移动顺序和暂存操作；
反转后正确连接边界，避免链表断裂。

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

LeetCode 138. 随机链表的复制：两种最优解法详解

掘金前端

作者 Wect

2026年2月13日 20:43

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）」建立「原节点 → 复制节点」的映射关系，解决“复制节点找不到对应随机指针指向”的问题。

两步走：

第一次遍历原链表：只创建复制节点，不处理指针，将原节点作为 key、复制节点作为 value 存入 Map，此时复制节点仅初始化了 val 值。
第二次遍历原链表：根据 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 指向，最后再将原链表和复制链表拆分。

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

原地插入复制节点：遍历原链表，在每个原节点 curr 后面插入一个复制节点 newNode（val 与 curr 一致），此时原链表变为「curr → newNode → curr.next（原next）」，不处理 random 指针。
给复制节点赋值 random：再次遍历原链表，当前原节点 curr 的复制节点是 curr.next，而 curr.random 的复制节点是 curr.random.next（因为第一步已在所有原节点后插入了复制节点），直接赋值即可。
拆分两个链表：最后遍历原链表，将原节点和复制节点拆分——原节点的 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 → 虽然构造函数有默认值，但建议明确赋值，避免隐式错误。

最后总结

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

新手入门优先掌握「哈希表映射法」，代码简洁、思路清晰，能快速解决问题，应对日常开发场景；
面试进阶需掌握「原地插入拆分法」，理解其指针操作逻辑和边界处理，体现对链表操作的深度掌握。