LeetCode 24 两两交换链表中的节点Swap Nodes in Pairs全解数组转换、递归与原地迭代三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕 LeetCode 24「两两交换链表中的节点Swap Nodes in Pairs」展开完整讲解数组转换、递归、原地迭代三种解法的直觉、算法步骤、多语言实现与复杂度分析并对照本仓库leetcode1/leetcode中python/0024-swap-nodes-in-pairs.py、java/0024-swap-nodes-in-pairs.java、go/0024-swap-nodes-in-pairs.go等真实提交源码深入剖析指针操作细节与常见陷阱。读完本文你将掌握链表两两交换的核心套路dummy 哨兵节点、保留下一对引用、奇数长度边界处理并能熟练迁移到其它链表重排类问题。问题回顾与前置知识题目要求给定一个单链表将每两个相邻节点交换位置并返回新链表的头节点。注意约束是只能修改节点的next指针不能修改节点的val值。例如输入head [1,2,3,4]输出应为[2,1,4,3]此示例见 c/0024-swap-nodes-in-pairs.c 头部注释。在动手之前需要具备以下基础链表基础Linked List Fundamentals理解单链表节点结构valnext、遍历方式以及指针修改的语义。各语言的节点定义在仓库各实现文件顶部的注释中均有给出例如 Python 的ListNode(val0, nextNone)、Go 的type ListNode struct { Val int; Next *ListNode }。原地指针操作In-Place Pointer Manipulation通过改变next指针来重排节点不依赖额外数据结构。Dummy 节点技巧Dummy Node Technique使用哨兵节点简化「头节点变化」时的边界处理。当头节点可能被替换时dummy.next始终指向最终的新头避免了大量特判。方法一转换为数组Convert To Array直觉最朴素的想法链表无法按下标随机访问但数组可以。先把链表节点全部收进数组利用下标直接交换相邻元素再按新顺序把节点重新串起来。该方案以空间换实现简单适合对指针操作不熟练时快速验证思路。算法步骤遍历链表把所有节点依次存入数组。以步长2遍历数组交换相邻两个元素。遍历数组把每个节点的next指向数组中下一个节点。将最后一个节点的next置为null返回数组第一个元素作为新头。核心代码Python 示例class Solution: def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]: if not head: return None arr [] cur head while cur: arr.append(cur) cur cur.next for i in range(0, len(arr) - 1, 2): arr[i], arr[i 1] arr[i 1], arr[i] for i in range(len(arr) - 1): arr[i].next arr[i 1] arr[-1].next None return arr[0]该思路的 C、Java、JavaScript、C#、Go、Kotlin、Swift、Rust 版本在原文的::tabs-start代码块中均已给出各语言仅容器 API 不同vector/ArrayList/List/[]/Vec核心逻辑完全一致。实现细节提示交换的是节点引用而非节点值因此交换后仍需按数组顺序重建next链并务必把末尾节点的next置空否则可能残留指向旧后继的引用如原列表末尾节点本来next就是null时无碍但交换后的末尾节点可能是原倒数第二个节点。复杂度分析时间复杂度$O(n)$遍历链表一次、交换一次、重建连接一次。空间复杂度$O(n)$需要额外数组存放全部节点指针。方法二递归Recursion直觉两两交换天然具有递归结构先交换前两个节点剩余链表从第三个节点开始交给递归处理。设当前对为cur第一个节点与nxt第二个节点那么cur.next应指向「剩余链表两两交换后的新头」nxt.next指向curnxt成为这对的新头。递归结构天然适配任意长度链表。算法步骤基准情形Base Case链表为空或只有一个节点时直接返回head。保存当前对引用cur headnxt head.next。递归交换从第三个节点开始的子链表并将其结果接到cur.next。令nxt.next cur完成本对的反转。返回nxt作为本对交换后的新头。核心代码Python 示例class Solution: def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head cur head nxt head.next cur.next self.swapPairs(nxt.next) nxt.next cur return nxt仓库源码佐证本仓库go/0024-swap-nodes-in-pairs.go提交的正是递归版本且用 Go 的平行赋值一行完成指针重排func swapPairs(head *ListNode) *ListNode { if head nil || head.Next nil { return head } next : head.Next swapped : swapPairs(next.Next) next.Next, head.Next head, swapped return next }对比可见go版本的next.Next, head.Next head, swapped等价于 Python 版本中nxt.next cur; cur.next swapPairs(nxt.next)两步但需注意 Go 平行赋值会先取右侧值再统一赋值顺序上天然安全而在 Rust 中则必须借助OptionBoxListNode的take()显式取出所有权见原文 Rust 代码块中的cur.next.take()/nxt.next.take()用法。复杂度分析时间复杂度$O(n)$每个节点恰好被访问一次。空间复杂度$O(n)$递归深度为 $\frac{n}{2}$占用调用栈空间。方法三原地迭代Iteration直觉用循环原地交换核心是仔细管理指针。引入 dummy 哨兵节点简化头节点变化每处理一对需要保存下一对起始引用、反转当前对内部指针、把前驱接到交换后的新头。每次前进两个节点保证每对恰好处理一次。这是面试中最推荐的解法时间 $O(n)$、空间 $O(1)$。算法步骤创建dummy节点指向head初始化prev dummycurr head。当curr与curr.next均存在时循环保存下一对起点nxtPair curr.next.next。识别本对第二个节点second curr.next。反转本对second.next currcurr.next nxtPair。前驱指向新头prev.next second。前进prev currcurr nxtPair。返回dummy.next。核心代码Python 示例class Solution: def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0, head) prev, curr dummy, head while curr and curr.next: nxtPair curr.next.next second curr.next # Reverse this pair second.next curr curr.next nxtPair prev.next second # Update pointers prev curr curr nxtPair return dummy.next仓库源码中的两种迭代写法本仓库同一题存在两种等价的迭代实现恰好印证了「dummy 节点」与「直接记录新头」两种边界处理思路写法 Adummy 哨兵 prev/curr 双指针python/0024-swap-nodes-in-pairs.pyclass Solution: def swapPairs(self, head: ListNode) - ListNode: dummy ListNode(0, head) prev, curr dummy, head while curr and curr.next: nxtPair curr.next.next second curr.next second.next curr curr.next nxtPair prev.next second prev curr curr nxtPair return dummy.next写法 B不设 dummy用new_head单独记录新头c/0024-swap-nodes-in-pairs.c 与 cpp/0024-swap-nodes-in-pairs.cppstruct ListNode* swapPairs(struct ListNode* head) { if (head NULL || head-next NULL) return head; struct ListNode *new_head head-next; struct ListNode *prev NULL; while (head ! NULL head-next ! NULL) { struct ListNode *next_pair head-next-next; struct ListNode *second head-next; if (prev ! NULL) prev-next second; second-next head; head-next next_pair; prev head; head next_pair; } return new_head; }两种写法的差异仅在边界处理写法 B 在循环外先用new_head head-next锁定新头因为第一对的第二个节点必然是最终新头循环内用if (prev ! NULL)处理首对写法 A 则让dummy.next永远指向新头代码更统一、更不易出错。java/0024-swap-nodes-in-pairs.java中则同时保留了迭代dummy 版与递归两个版本供对照学习。复杂度分析时间复杂度$O(n)$单次遍历。空间复杂度$O(1)$仅使用常数个指针变量。常见陷阱Common Pitfalls陷阱一丢失下一对链表的引用交换当前对之前必须先把curr.next.next下一对起点保存下来。如果先做内部反转curr.next已被改写剩余链表将彻底丢失。正确做法每次循环开头立即执行nxtPair curr.next.next。陷阱二忘记更新前驱节点的next指针交换完一对之后前驱节点首对时为 dummy必须指向交换后的新头即second。常见错误是只把对内部两个节点反转正确却忘了把前驱接回链表导致链断裂、节点丢失。这正是引入prev或dummy指针的意义所在。陷阱三没有处理奇数长度链表当链表节点数为奇数时最后一个节点没有配对对象应保持原位不动。循环条件必须同时校验curr与curr.next都存在只检查其中一个会导致空指针异常如 Java/C/C 直接解引用null或末节点被错误处理。仓库中所有实现如 go/0024-swap-nodes-in-pairs.go 的head nil || head.Next nil都严格遵循了这一边界检查。三种解法对比总结方法思路时间复杂度空间复杂度适用场景转换为数组下标交换后重建链接$O(n)$$O(n)$快速验证思路、教学演示递归先交换前两个再递归处理剩余$O(n)$$O(n)$调用栈代码简洁、逻辑直观原地迭代dummy 指针反转$O(n)$$O(1)$面试与生产首选空间最优三种方法都满足题目「只能修改节点指针、不能改值」的约束。若想进一步巩固链表指针操作可继续练习本仓库中同族的题目reverse-a-linked-list.md、reverse-nodes-in-k-group.mdk2 时即本题、swap-nodes-in-pairs 的相邻变体 swapping-nodes-in-a-linked-list其中 java/1721-swapping-nodes-in-a-linked-list.java 等文件展示了另一种「交换节点值」而非「交换节点」的思路差异。掌握本题的 dummy 节点与指针保存技巧后这些进阶题都能迎刃而解。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考