一、链表基础知识1. 链表的定义链表是一种非线性连续、逻辑有序、物理离散的线性数据结构。链表以独立节点为基本存储单元每个节点包含数据域与指针域依靠指针域记录下一节点的逻辑地址以此串联成完整的线性结构。与数组物理连续存储不同链表节点在内存中随机分布仅通过指针维系逻辑顺序。2. 链表的结构特性单链表整体由头节点、中间节点和尾节点组成。头节点是链表的唯一访问入口所有遍历、修改操作均需从头节点启动。尾节点的指针域为空代表链表的终止位置。链表不具备下标索引机制不支持随机访问只能通过顺序遍历的方式从头部至尾部依次查找目标节点。3. 链表操作核心准则链表所有结构性修改操作都遵循固定核心原则。在变更任意节点的指针指向前必须预先保存后续链表的节点信息避免出现断链问题导致后半段链表数据丢失。链表的插入、删除、反转等操作本质均为指针指向的重构无需移动节点数据仅修改节点间的逻辑关联。4. 虚拟头节点的功能原理常规链表的头节点可被删除或替换会产生特殊的边界逻辑增加操作复杂度。虚拟头节点是无有效数据的辅助节点挂载在真实链表最前端。其核心作用是统一链表头部、中部、尾部的操作逻辑消除头节点变动带来的特殊判断简化链表结构操作的整体逻辑降低边界错误概率。5. 链表与数组的特性对比数组物理内存连续支持随机访问查询读取效率极高但元素增删时需要批量迁移后续所有元素执行效率较低。链表物理内存离散仅支持顺序遍历查找效率偏低但结构修改仅需调整两处指针关系无需移动大量数据适用于频繁增删、动态调整结构的业务场景。二、链表递归核心理论1. 链表递归核心思想链表递归的核心逻辑为自上而下拆分问题自下而上求解问题。将整条长链表的复杂操作问题拆解为后半段子链表的子问题不断缩小问题规模直至满足终止条件。在子链表全部处理完成后逐层回溯修正当前节点的指针结构最终完成整条链表的变换重构。2. 递归终止基线条件递归必须设置固定终止条件杜绝无限递归。链表递归通用基线条件为两种情况一是当前链表为空无任何节点需要处理二是当前链表仅有单个节点结构天然合法无需修改。满足以上条件时直接返回当前节点终止向下递推的过程。3. 递推阶段运行逻辑递推阶段仅负责问题拆分不进行任何结构修改。每一层递归都会优先忽略当前节点深度递归处理当前节点后方的所有子链表。程序持续向链表尾部迭代深入不断简化问题规模将所有链表结构调整工作全部留存至回溯阶段执行。4. 回溯阶段运行逻辑递推触达链表终止条件后程序开启逐层回溯流程。此时每一层对应的子链表已完全处理完毕结构符合题目要求。当前层级只需基于已完成处理的子链表重新调整自身节点的指针连接关系完成局部结构修正最终向上返回重构后的链表头节点。5. 递归与迭代的本质区别迭代采用正向遍历逻辑自链表头部向尾部逐步修改结构依靠循环指针完成操作不占用系统栈空间无溢出风险但指针操作逻辑繁琐复杂。递归采用逆向修改逻辑自链表尾部向头部重构结构依靠函数栈保存节点信息逻辑简洁统一、通用性强但链表长度过大时嵌套层数超标会引发栈溢出问题。6. 链表递归通用解题思维解决链表递归题目遵循固定三步思维。第一步明确递归终止的边界条件确定无需处理的基础链表形态。第二步界定子问题范围将后半段子链表交由递归函数独立处理。第三步依托子链表的处理结果重构当前节点的指针关联完成局部优化并返回新的链表头部。反转链表 对应LeetCode 206两两交换链表中的节点 对应LeetCode 24