 空间的原地重排)
LeetCode 328 奇偶链表题解一次遍历 双指针实现 O(1) 空间的原地重排【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 LeetCode 328「奇偶链表Odd Even Linked List」为核心系统讲解如何用一次遍历、两个指针原地把单链表的奇数位节点与偶数位节点重排到一起在满足空间复杂度 O(1)、时间复杂度 O(N) 的同时保持节点相对顺序。读者读完将掌握「双虚拟节点 双指针拆分 尾部拼接」这一链表重组范式并能将其迁移到 86. 分隔链表等同类题目中。本文内容以仓库题解 problems/328.odd-even-linked-list.md 为骨架并结合仓库的链表专题与相关题解源码进行纵深印证。题目概述题目描述给定一个单链表把所有的奇数节点和偶数节点分别排在一起。请注意这里的奇数节点和偶数节点指的是节点编号的奇偶性而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)时间复杂度应为 O(nodes)nodes 为节点总数。示例与说明示例 1:输入: 1-2-3-4-5-NULL 输出: 1-3-5-2-4-NULL示例 2:输入: 2-1-3-5-6-4-7-NULL 输出: 2-3-6-7-1-5-4-NULL说明:应当保持奇数节点和偶数节点的相对顺序。链表的第一个节点视为奇数节点第二个节点视为偶数节点以此类推。该题在仓库题解目录索引 SUMMARY.md 中登记为0328. 奇偶链表属于链表类高频面试题原题解中记录的常考公司包括阿里、腾讯、百度、字节。前置知识与考查点本题核心前置知识是链表具体涉及链表节点的指针引用与重新挂接node.next的改写头节点边界的处理原地算法in-place的含义不新建链表、不借助数组等额外存储仅通过调整指针完成重排。仓库的链表专题开篇就指出链表是物理存储上非连续、非顺序的结构其逻辑顺序通过指针链接次序实现因此链表题目本质上就是指针的搬运插入操作在给定前驱指针时时间复杂度为 O(1)删除操作只需将前驱的next修正为下下个节点。本题正是这一特性的极致运用——整个算法只做指针改写不分配任何新节点。思路分析从朴素两遍遍历到单次遍历双指针朴素思路及其两个问题符合直觉的想法是先遍历一遍找出奇数节点再遍历一遍找出偶数节点最后串起来。但原题解指出这样做有两个问题如果不修改节点则需要借助额外的空间来暂存节点空间复杂度退化为 O(N)不满足题目 O(1) 的硬性要求如果修改节点在第一次遍历时切断指针会对第二次遍历遍历偶数节点造成影响——因为第一次遍历已经破坏了原链表的链接结构。一次遍历、同时拆两根链的方案因此可以采用一种更优做法遍历一次每一步同时修改两个节点一个奇数节点、一个偶数节点这样就可以同时规避上面两个问题整个过程只新建两个虚拟节点不复制数据节点空间复杂度保持 O(1)奇数链与偶数链的拆分在同一趟遍历中同步完成不存在二次遍历被破坏结构的问题遍历结束后把偶数链的头部接到奇数链的尾部即完成重排。本质上这是把一条链表原地拆分成「奇数位链」和「偶数位链」两条子链再首尾相接。这个「一次遍历、双指针、双链并行推进」的手法与仓库中 86. 分隔链表 的题解思路完全同构后文会做对照。关键点解析原题解总结了两个关键点1. 用虚拟节点来简化操作两个虚拟节点分别作为奇数链与偶数链的「哨兵头」dummyHead1的next指向原链表头奇数链起点dummyHead2的next指向head.next偶数链起点。之所以引入虚拟节点是因为链表的头节点是最常见的边界条件。仓库链表专题对此有系统论述用一个虚拟头指向头节点后虚拟头就成为新的头节点而虚拟头不是题目给的节点、不参与运算因此不需要为头节点做特殊判断见该文档「虚拟节点」相关小节在本题场景中奇数链的最终头节点就是原链表头而偶数链的头节点是head.next两者都可能是空指针或需要被返回的指针用 dummy 统一后无论怎么拆链dummyHead1.next永远能取到正确的奇数链头dummyHead2.next永远能取到正确的偶数链头。2. 循环结束条件设置为odd odd.next even even.next原题解特别强调循环结束条件不应该是odd even否则需要在循环结束后额外记录一下奇数节点的最后一个节点操作会变复杂。原因在于循环体内通过odd.next oddNext来推进奇数链如果循环结束时odd恰好是空指针链表节点数为偶数时最后一轮oddNext为 null那么循环体之后执行odd.next dummyHead2.next就会对空指针解引用、产生空指针异常。而把结束条件收紧为四者皆非空可以保证循环退出时odd一定非空否则无法进入循环体的赋值从而让循环之后的odd.next dummyHead2.next安全成立。C 版的循环条件为什么可以简化原题解的 C 版本循环条件只写了even even-next并且注释说明了原因每次循环之后依然保持 odd 在 even 之前。因为循环体内先执行odd-next even-next; odd odd-next;再执行even-next odd-next; even even-next;奇数指针永远先于偶数指针更新且位于偶数指针之前。因此只要even非空其前面的odd必然非空只需判断even一条链即可同时odd-next evenHead在退出循环后也必然安全odd 非空。两种写法殊途同归JS 版判断更保守直观C 版更精简是同一循环不变量的两种表达。代码实现与逐步推演JavaScript 实现原题解完整代码JS/* * lc appleetcode id328 langjavascript * * [328] Odd Even Linked List * */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} head * return {ListNode} */ var oddEvenList function (head) { if (!head || !head.next) return head; const dummyHead1 { next: head, }; const dummyHead2 { next: head.next, }; let odd dummyHead1.next; let even dummyHead2.next; while (odd odd.next even even.next) { const oddNext odd.next.next; const evenNext even.next.next; odd.next oddNext; even.next evenNext; odd oddNext; even evenNext; } odd.next dummyHead2.next; return dummyHead1.next; };C 实现原题解完整代码C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* oddEvenList(ListNode* head) { if (head nullptr) return head; auto odd head, evenHead head-next, even head-next; // 因为每次循环之后依然保持odd在even之前循环条件可以只判断even和even-next是否为空修改odd和even的指向的操作也可以简化 while (even ! nullptr even-next ! nullptr) { odd-next even-next; odd odd-next; even-next odd-next; even even-next; } odd-next evenHead; return head; } };语言支持原题解标注为 JS、C。两个版本在循环退出后都需要执行「奇数链尾接偶数链头」的拼接操作JS 用odd.next dummyHead2.nextC 用odd-next evenHead。示例 1 的逐步推演以1-2-3-4-5-NULL为例采用 JS 版本指针语义轮次循环前状态oddNext / evenNext执行后链接指针推进初始odd1, even2———第 1 轮odd1, even23 / 41-3,2-4odd3, even4第 2 轮odd3, even45 / null3-5,4-NULLodd5, evennull第 3 轮odd5但 odd.next 为 null循环条件不满足退出———拼接odd.next dummyHead2.next即5-2———最终链表为1-3-5-2-4-NULL与示例输出一致。奇数位节点 1、3、5 与偶数位节点 2、4 的相对顺序均保持不变满足题目说明要求。复杂度分析原题解给出的复杂度结论时间复杂度$O(N)$其中 N 为链表节点总数。整个算法只做一次遍历循环内每次迭代处理两个节点、执行常数次指针赋值空间复杂度$O(1)$。除两个虚拟节点不含数据、仅作为哨兵与若干指针变量外不申请任何额外空间也不复制任何数据节点属于严格的原地算法。从仓库链表专题的复杂度论述看链表操作之所以能做到如此轻量正是因为它不像数组那样需要搬移连续内存指针改写即为「搬运」这也是本题能同时满足 O(1) 空间与 O(N) 时间的原因。源码佐证仓库中的同类链表重组范式虚拟节点技巧的专题论述仓库链表专题在多个小节对本题用到的技巧给出了系统性解释可作为本题解法的原理佐证关于边界处理「如果题目的头节点可能被移除那么考虑使用虚拟节点这样头节点就变成了中间节点就不需要为头节点做特殊判断了」——本题虽然头节点不会被移除但偶数链头head.next在空链表、单节点链表场景下需要特殊判断dummy 统一规避了这类分支关于虚拟头的本质「我们用一个虚拟头指向头节点虚拟头就是新的头节点了而虚拟头不是题目给的节点不参与运算因此不需要特殊判断」关于返回中间节点可以借助虚拟头「在恰当的时候断开连接然后返回虚拟头的 next」本题最后返回dummyHead1.next正是这一模式。与 86. 分隔链表的手法同构86. 分隔链表 是仓库中与本题结构高度相似的题解其思路同样包含三步设定两个虚拟节点dummyHead1、dummyHead2分别保存「小于 x 的链表」与「大于等于 x 的链表」遍历整个原始链表将节点按条件分别挂入两条链遍历结束后将dummyHead2插入到dummyHead1后面返回dummyHead1.next。对照可见86. 分隔链表 与本题328. 奇偶链表共享完全相同的解题骨架——双虚拟节点 单次遍历分组 尾部拼接区别仅在于分组依据本题按「节点编号奇偶」分组1、3、5… 与 2、4、6…86 题按「节点值与阈值 x 的关系」分组。掌握 328 的写法即可直接迁移到 86 题反之亦然。这正是仓库题解体系中「一类题一个范式」的体现相关索引可分别见 SUMMARY.md 与题解目录 problems 下的对应文件。延伸思考与变体空链表与单节点链表两版代码开头均有if (!head || !head.next) return head;的边界保护分别对应空链表与仅一个节点无偶数节点的情况此时无需任何重排直接返回。节点数为偶数的情况如1-2-3-4-NULL第 2 轮后 odd3、evennull 退出odd.next dummyHead2.next使3-2得到1-3-2-4-NULL重排正确。变体按值分类而非按位分类若题目改为「把值小于 x 的节点排在前面」解法即为上文对照的 86. 分隔链表若改为「链表节点按奇偶值分组」则分组依据从「迭代位置」换成「节点值奇偶」骨架代码几乎不变只改判断条件。延伸K 路分组将「奇数/偶数」推广为「按编号模 K 分组」可扩展为 K 个 dummy 头 一轮遍历的 K 路拆分时间复杂度仍为 O(N)空间 O(1)K 个哨兵节点这是本题范式在更复杂场景下的自然推广。综上本题的核心价值不在于记住一段代码而在于领会「单次遍历 双指针同步拆链 虚拟节点兜底边界」的链表重排范式——它同时满足了 O(N) 时间、O(1) 空间与保持相对顺序三个约束是原地操作链表类题目的代表性解法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 328 奇偶链表题解：一次遍历 + 双指针实现 O(1) 空间的原地重排
LeetCode 328 奇偶链表题解一次遍历 双指针实现 O(1) 空间的原地重排【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 LeetCode 328「奇偶链表Odd Even Linked List」为核心系统讲解如何用一次遍历、两个指针原地把单链表的奇数位节点与偶数位节点重排到一起在满足空间复杂度 O(1)、时间复杂度 O(N) 的同时保持节点相对顺序。读者读完将掌握「双虚拟节点 双指针拆分 尾部拼接」这一链表重组范式并能将其迁移到 86. 分隔链表等同类题目中。本文内容以仓库题解 problems/328.odd-even-linked-list.md 为骨架并结合仓库的链表专题与相关题解源码进行纵深印证。题目概述题目描述给定一个单链表把所有的奇数节点和偶数节点分别排在一起。请注意这里的奇数节点和偶数节点指的是节点编号的奇偶性而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)时间复杂度应为 O(nodes)nodes 为节点总数。示例与说明示例 1:输入: 1-2-3-4-5-NULL 输出: 1-3-5-2-4-NULL示例 2:输入: 2-1-3-5-6-4-7-NULL 输出: 2-3-6-7-1-5-4-NULL说明:应当保持奇数节点和偶数节点的相对顺序。链表的第一个节点视为奇数节点第二个节点视为偶数节点以此类推。该题在仓库题解目录索引 SUMMARY.md 中登记为0328. 奇偶链表属于链表类高频面试题原题解中记录的常考公司包括阿里、腾讯、百度、字节。前置知识与考查点本题核心前置知识是链表具体涉及链表节点的指针引用与重新挂接node.next的改写头节点边界的处理原地算法in-place的含义不新建链表、不借助数组等额外存储仅通过调整指针完成重排。仓库的链表专题开篇就指出链表是物理存储上非连续、非顺序的结构其逻辑顺序通过指针链接次序实现因此链表题目本质上就是指针的搬运插入操作在给定前驱指针时时间复杂度为 O(1)删除操作只需将前驱的next修正为下下个节点。本题正是这一特性的极致运用——整个算法只做指针改写不分配任何新节点。思路分析从朴素两遍遍历到单次遍历双指针朴素思路及其两个问题符合直觉的想法是先遍历一遍找出奇数节点再遍历一遍找出偶数节点最后串起来。但原题解指出这样做有两个问题如果不修改节点则需要借助额外的空间来暂存节点空间复杂度退化为 O(N)不满足题目 O(1) 的硬性要求如果修改节点在第一次遍历时切断指针会对第二次遍历遍历偶数节点造成影响——因为第一次遍历已经破坏了原链表的链接结构。一次遍历、同时拆两根链的方案因此可以采用一种更优做法遍历一次每一步同时修改两个节点一个奇数节点、一个偶数节点这样就可以同时规避上面两个问题整个过程只新建两个虚拟节点不复制数据节点空间复杂度保持 O(1)奇数链与偶数链的拆分在同一趟遍历中同步完成不存在二次遍历被破坏结构的问题遍历结束后把偶数链的头部接到奇数链的尾部即完成重排。本质上这是把一条链表原地拆分成「奇数位链」和「偶数位链」两条子链再首尾相接。这个「一次遍历、双指针、双链并行推进」的手法与仓库中 86. 分隔链表 的题解思路完全同构后文会做对照。关键点解析原题解总结了两个关键点1. 用虚拟节点来简化操作两个虚拟节点分别作为奇数链与偶数链的「哨兵头」dummyHead1的next指向原链表头奇数链起点dummyHead2的next指向head.next偶数链起点。之所以引入虚拟节点是因为链表的头节点是最常见的边界条件。仓库链表专题对此有系统论述用一个虚拟头指向头节点后虚拟头就成为新的头节点而虚拟头不是题目给的节点、不参与运算因此不需要为头节点做特殊判断见该文档「虚拟节点」相关小节在本题场景中奇数链的最终头节点就是原链表头而偶数链的头节点是head.next两者都可能是空指针或需要被返回的指针用 dummy 统一后无论怎么拆链dummyHead1.next永远能取到正确的奇数链头dummyHead2.next永远能取到正确的偶数链头。2. 循环结束条件设置为odd odd.next even even.next原题解特别强调循环结束条件不应该是odd even否则需要在循环结束后额外记录一下奇数节点的最后一个节点操作会变复杂。原因在于循环体内通过odd.next oddNext来推进奇数链如果循环结束时odd恰好是空指针链表节点数为偶数时最后一轮oddNext为 null那么循环体之后执行odd.next dummyHead2.next就会对空指针解引用、产生空指针异常。而把结束条件收紧为四者皆非空可以保证循环退出时odd一定非空否则无法进入循环体的赋值从而让循环之后的odd.next dummyHead2.next安全成立。C 版的循环条件为什么可以简化原题解的 C 版本循环条件只写了even even-next并且注释说明了原因每次循环之后依然保持 odd 在 even 之前。因为循环体内先执行odd-next even-next; odd odd-next;再执行even-next odd-next; even even-next;奇数指针永远先于偶数指针更新且位于偶数指针之前。因此只要even非空其前面的odd必然非空只需判断even一条链即可同时odd-next evenHead在退出循环后也必然安全odd 非空。两种写法殊途同归JS 版判断更保守直观C 版更精简是同一循环不变量的两种表达。代码实现与逐步推演JavaScript 实现原题解完整代码JS/* * lc appleetcode id328 langjavascript * * [328] Odd Even Linked List * */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} head * return {ListNode} */ var oddEvenList function (head) { if (!head || !head.next) return head; const dummyHead1 { next: head, }; const dummyHead2 { next: head.next, }; let odd dummyHead1.next; let even dummyHead2.next; while (odd odd.next even even.next) { const oddNext odd.next.next; const evenNext even.next.next; odd.next oddNext; even.next evenNext; odd oddNext; even evenNext; } odd.next dummyHead2.next; return dummyHead1.next; };C 实现原题解完整代码C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* oddEvenList(ListNode* head) { if (head nullptr) return head; auto odd head, evenHead head-next, even head-next; // 因为每次循环之后依然保持odd在even之前循环条件可以只判断even和even-next是否为空修改odd和even的指向的操作也可以简化 while (even ! nullptr even-next ! nullptr) { odd-next even-next; odd odd-next; even-next odd-next; even even-next; } odd-next evenHead; return head; } };语言支持原题解标注为 JS、C。两个版本在循环退出后都需要执行「奇数链尾接偶数链头」的拼接操作JS 用odd.next dummyHead2.nextC 用odd-next evenHead。示例 1 的逐步推演以1-2-3-4-5-NULL为例采用 JS 版本指针语义轮次循环前状态oddNext / evenNext执行后链接指针推进初始odd1, even2———第 1 轮odd1, even23 / 41-3,2-4odd3, even4第 2 轮odd3, even45 / null3-5,4-NULLodd5, evennull第 3 轮odd5但 odd.next 为 null循环条件不满足退出———拼接odd.next dummyHead2.next即5-2———最终链表为1-3-5-2-4-NULL与示例输出一致。奇数位节点 1、3、5 与偶数位节点 2、4 的相对顺序均保持不变满足题目说明要求。复杂度分析原题解给出的复杂度结论时间复杂度$O(N)$其中 N 为链表节点总数。整个算法只做一次遍历循环内每次迭代处理两个节点、执行常数次指针赋值空间复杂度$O(1)$。除两个虚拟节点不含数据、仅作为哨兵与若干指针变量外不申请任何额外空间也不复制任何数据节点属于严格的原地算法。从仓库链表专题的复杂度论述看链表操作之所以能做到如此轻量正是因为它不像数组那样需要搬移连续内存指针改写即为「搬运」这也是本题能同时满足 O(1) 空间与 O(N) 时间的原因。源码佐证仓库中的同类链表重组范式虚拟节点技巧的专题论述仓库链表专题在多个小节对本题用到的技巧给出了系统性解释可作为本题解法的原理佐证关于边界处理「如果题目的头节点可能被移除那么考虑使用虚拟节点这样头节点就变成了中间节点就不需要为头节点做特殊判断了」——本题虽然头节点不会被移除但偶数链头head.next在空链表、单节点链表场景下需要特殊判断dummy 统一规避了这类分支关于虚拟头的本质「我们用一个虚拟头指向头节点虚拟头就是新的头节点了而虚拟头不是题目给的节点不参与运算因此不需要特殊判断」关于返回中间节点可以借助虚拟头「在恰当的时候断开连接然后返回虚拟头的 next」本题最后返回dummyHead1.next正是这一模式。与 86. 分隔链表的手法同构86. 分隔链表 是仓库中与本题结构高度相似的题解其思路同样包含三步设定两个虚拟节点dummyHead1、dummyHead2分别保存「小于 x 的链表」与「大于等于 x 的链表」遍历整个原始链表将节点按条件分别挂入两条链遍历结束后将dummyHead2插入到dummyHead1后面返回dummyHead1.next。对照可见86. 分隔链表 与本题328. 奇偶链表共享完全相同的解题骨架——双虚拟节点 单次遍历分组 尾部拼接区别仅在于分组依据本题按「节点编号奇偶」分组1、3、5… 与 2、4、6…86 题按「节点值与阈值 x 的关系」分组。掌握 328 的写法即可直接迁移到 86 题反之亦然。这正是仓库题解体系中「一类题一个范式」的体现相关索引可分别见 SUMMARY.md 与题解目录 problems 下的对应文件。延伸思考与变体空链表与单节点链表两版代码开头均有if (!head || !head.next) return head;的边界保护分别对应空链表与仅一个节点无偶数节点的情况此时无需任何重排直接返回。节点数为偶数的情况如1-2-3-4-NULL第 2 轮后 odd3、evennull 退出odd.next dummyHead2.next使3-2得到1-3-2-4-NULL重排正确。变体按值分类而非按位分类若题目改为「把值小于 x 的节点排在前面」解法即为上文对照的 86. 分隔链表若改为「链表节点按奇偶值分组」则分组依据从「迭代位置」换成「节点值奇偶」骨架代码几乎不变只改判断条件。延伸K 路分组将「奇数/偶数」推广为「按编号模 K 分组」可扩展为 K 个 dummy 头 一轮遍历的 K 路拆分时间复杂度仍为 O(N)空间 O(1)K 个哨兵节点这是本题范式在更复杂场景下的自然推广。综上本题的核心价值不在于记住一段代码而在于领会「单次遍历 双指针同步拆链 虚拟节点兜底边界」的链表重排范式——它同时满足了 O(N) 时间、O(1) 空间与保持相对顺序三个约束是原地操作链表类题目的代表性解法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考