两两交换链表中的节点：AlgoNote 解题手册中 LeetCode 0024 的哑节点与三指针迭代法全解析

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文以 AlgoNote算法通关手册中「0024. 两两交换链表中的节点」题解为主体结合仓库内链表基础章节与 Python 源码实现系统拆解这道中等难度链表题的两类核心解法基于哑节点dummy node与三指针的迭代法以及标准递归法。读完本文你将掌握真正交换节点、而非交换节点值的指针重连技巧理解哑节点在链表头部操作中的关键作用并能将同样的套路迁移到「K 个一组翻转链表」等进阶题目中。1. 题目速览输入输出与约束条件「0024. 两两交换链表中的节点」是链表模块中一道经典的中等难度题目标签为「递归、链表」。题目描述给定一个链表的头节点head要求按顺序将链表中每两个节点交换一下并返回交换后的链表头节点。说明与约束必须实际进行节点交换而不是只改变节点内部的值链表中节点的数目在范围 $[0, 100]$ 内$0 \le Node.val \le 100$。示例示例 1输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]。题目隐含了一个易被忽略的前提链表长度既可能为偶数恰好两两成对也可能为奇数末尾落单节点保持原位置不动这与「K 个一组翻转链表」中最后剩余节点保持原有顺序的要求同源——本题可视为 k 2 的特例。2. 题意剖析为什么交换节点值是错误解法题面特别强调需要实际进行节点交换而不是纸改变节点内部的值原文档原文。这一约束揭示了两层含义算法题严谨性仅交换node.val虽然能通过输出比对但并没有改变链表的结构关系与题目考察的指针操作能力背道而驰工程意义在实际系统中链表节点往往承载着额外字段指针、引用、复杂对象直接搬运值不可行必须通过重连next指针来重组结构。链表节点的基础结构在仓库源码 codes/python/02_linked_list/linked_list.py 中定义如下class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这与 链表基础知识 中「链节点类ListNode包含成员变量val和next」的描述完全一致。交换两个节点本质就是调整next指针的指向关系让它们在链表中的逻辑顺序发生互换。3. 思路一迭代法——哑节点 三指针这是原题解文档给出的主解法核心是用哑节点规避头节点无前驱的边界问题再用三个指针完成一轮交换。3.1 核心思想单链表只能单向遍历若要交换节点node1与node2必须同时知道待交换节点的前驱节点。当待交换的正是链表的头两个节点时head之前没有节点直接处理会非常别扭。解法是创建哑节点new_head令new_head.next head此时哑节点充当头节点的前驱用curr指向当前处理到的前驱节点node1指向第一个待交换节点node2指向第二个待交换节点通过三步指针重连将curr → node1 → node2的指向关系变为curr → node2 → node1移动curr到下一对待交换节点的前驱位置循环处理直至剩余节点不足两个。3.2 逐步拆解指针操作初始状态curr → node1 → node2 → (node2.next)第一步curr.next node2让前驱直接指向第二个节点第二步node1.next node2.next先保存并接好node1的后继否则下一步会丢失node2.next这段链表第三步node2.next node1让第二个节点回头指向第一个节点。此时链表现为curr → node2 → node1 → (原 node2.next)完成一次交换。关键在于第二步必须先于第三步执行否则node2.next的原始指向会在node2.next node1时被覆盖导致链表断裂。3.3 完整可运行代码原题解文档给出的迭代法实现如下class Solution: def swapPairs(self, head: ListNode) - ListNode: new_head ListNode(0) new_head.next head curr new_head while curr.next and curr.next.next: node1 curr.next node2 curr.next.next curr.next node2 node1.next node2.next node2.next node1 curr node1 return new_head.next逐行解读ListNode(0)创建哑节点值取0仅作占位实际交换过程中不参与逻辑判断循环条件curr.next and curr.next.next同时保证链表非空剩余节点 ≥ 1、至少存在两个可交换节点。若链表为[]或[1]单节点循环直接不进入node1 curr.next与node2 curr.next.next分别锁定当前一对待交换节点三步重连完成后curr node1——此时node1已处于交换后一对节点中的后位恰好是下一对待交换节点的前驱最终返回new_head.next即原链表新的头节点。3.4 复杂度分析时间复杂度$O(n)$其中 $n$ 为链表节点数量。每个节点恰好被指针经过常数次整体为单次线性遍历空间复杂度从实现代码看仅使用new_head、curr、node1、node2四个指针变量属于 $O(1)$ 额外空间。原题解文档标注为 $O(n)$从源码结构分析应更准确地理解为 $O(1)$——迭代法不依赖递归栈也不创建任何与 $n$ 相关的辅助结构。4. 边界情况与易错点清单迭代法实现简洁但面试中高频的追问都集中在边界处理上场景行为原因head []空链表返回[]循环条件不成立直接返回new_head.next即None链表只有 1 个节点返回原链表没有第二个节点可交换链表长度为奇数末尾单个节点保持原位最后不足一对循环自然退出头两个节点交换由哑节点兜底哑节点使curr始终存在前驱语义三个最常见的错误写法先执行node2.next node1再执行node1.next node2.next此时node2.next已被改写node2.next不再是原链表的后继链表发生断裂忘记更新curr循环会无限重复交换同一对节点不创建哑节点、单独特判头节点代码会出现if分支逻辑重复且易错——这正是哑节点技巧存在的意义。关于哑节点虚拟头节点的设计思想可参见 链表基础知识 中对头节点插入/删除的特判说明仓库源码 linked_list.py 中的insertFront头部插入也体现了需要额外处理头节点的场景。5. 思路二递归解法延伸补充原题解文档仅给出迭代法但题目标签包含「递归」。递归解法的思路是先把后面链表的交换结果处理好再回头交换头两个节点。若head为空或只有一个节点直接返回否则交换head与head.next并将head接到递归处理结果的前面。class Solution: def swapPairs(self, head: ListNode) - ListNode: # 递归终止条件链表为空或只剩一个节点 if not head or not head.next: return head # 保存第二个节点 second head.next # 递归处理剩余链表结果接到第一个节点之后 head.next self.swapPairs(second.next) # 第二个节点成为新的头节点 second.next head return second执行过程以[1,2,3,4]为例递归到最深处(3,4)second 43.next swapPairs(None) None4.next 3返回4回溯到(1,2)second 21.next 4上一步返回值2.next 1返回2最终链为2 → 1 → 4 → 3。复杂度时间复杂度 $O(n)$空间复杂度 $O(n)$因为递归深度最多为 $\frac{n}{2}$ 层若按调用链计算则不超过 $n$ 层每层消耗栈空间。当链表很长时递归可能引发栈溢出风险这也是迭代法通常更受青睐的原因。递归处理链表的通用范式可对照 反转链表 中的递归解法理解。6. 从仓库源码看链表指针操作的底层一致性仓库的链表实现 codes/python/02_linked_list/linked_list.py 中「中间插入」与「中间删除」操作与本题共享同一套指针操作原则# 中间插入先连后继再接前驱 node ListNode(val) node.next cur.next cur.next node # 中间删除前驱直接跳过目标节点 del_node cur.next cur.next del_node.next核心规律是在修改某个节点的next指针之前先用临时变量或先完成其他指针的更新保住将要丢失的引用。本题迭代法中node1.next node2.next正是这条原则的体现——先接好后续链表再回头重连node2。理解了这条底层原则两两交换、区间反转、K 组翻转等链表题都可以统一到同一套心智模型下。另外链表基础知识 总结的链表特性也解释了本题的复杂度来源链表不支持随机访问只能从头顺序遍历因此任何需要定位节点的操作都是 $O(n)$但在已知前驱节点的前提下插入/删除/交换操作本身只需要 $O(1)$ 的指针改动——本题的curr指针正是已知前驱的载体。7. 举一反三与 K 个一组翻转链表等题目的关联「0025. K 个一组翻转链表」要求每k个节点一组翻转当k 2时其结果与本题完全一致例如[1,2,3,4,5]在 k2 下输出[2,1,4,3,5]。两道题共享三个关键技巧哑节点dummy_head.next head规避反转区间包含头节点时找不到前驱的问题区间定位用index计数器或指针推进确定待处理区间边界指针重连顺序先保存后继next cur.next再翻转指向cur.next pre最后同步推进两个指针——这与 反转链表 迭代法的四步操作完全一致。按难度递进建议的学习路径是反转链表整链反转→ 反转链表 II区间反转→ 本题两两交换→ K 个一组翻转链表分组反转。掌握了本题的哑节点 指针重连向上可轻松理解 K 组翻转向下可直接对应链表基础操作中的插入与删除实现。8. 总结本题虽为中等难度却是检验链表基本功的高频面试题。要点归纳如下必须实际交换节点通过重连next指针改变节点逻辑顺序而非交换val迭代法借助哑节点规避头节点前驱问题以curr / node1 / node2三指针完成一轮交换时间复杂度 $O(n)$、额外空间 $O(1)$指针操作顺序是正确性的关键先保存并接好node1的后继再让node2回头指向node1边界情况包括空链表、单节点链表、奇数长度链表全部由循环条件curr.next and curr.next.next天然兜底递归法是题目标签对应的另一种标准解法思路为先递归处理尾部、再交换头部代价是 $O(n)$ 栈空间。本文所涉解法均收录于 AlgoNote 仓库的 swap-nodes-in-pairs.md 题解文档可配合 链表基础知识 与 链表双指针 章节系统学习并在 codes/python/02_linked_list/linked_list.py 中通过ListNode类与插入/删除方法巩固对指针操作的理解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 24 两两交换链表中的节点dummy 虚拟头节点与递归/迭代多语言解法全解析LeetCode 24 两两交换链表中的节点dummy 虚拟头节点与递归/迭代多语言解法全解析 本文以 leetcode 题解仓库GitHub 加速计划 /文档教程知识库LeetCode-Go 题解 0024Swap Nodes in Pairs两两交换链表中的节点Go 实现详解LeetCode Go 题解 0024Swap Nodes in Pairs两两交换链表中的节点Go 实现详解 导读 本文以 LeetCode Go 仓库示例工程LeetCode 24 两两交换链表中的节点Swap Nodes in Pairs全解数组转换、递归与原地迭代三种解法LeetCode 24 两两交换链表中的节点Swap Nodes in Pairs全解数组转换、递归与原地迭代三种解法 本文围绕 LeetCode 24「示例工程教程上一篇cyberdog_ros2进阶技巧参数配置与节点调试实用方法下一篇高德地图Qt插件开发实战跨平台地图应用完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考