企业官网建设流程全解析

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修正为下下个节点。本题正是这一特性的极致运用——整个算法只做指针改写，不分配任何新节点。

思路分析：从朴素两遍遍历到单次遍历双指针

朴素思路及其两个问题

符合直觉的想法是：先遍历一遍找出奇数节点，再遍历一遍找出偶数节点，最后串起来。

但原题解指出这样做有两个问题：

1. 如果不修改节点，则需要借助额外的空间来暂存节点，空间复杂度退化为 O(N)，不满足题目 O(1) 的硬性要求；
2. 如果修改节点（在第一次遍历时切断指针），会对第二次遍历（遍历偶数节点）造成影响——因为第一次遍历已经破坏了原链表的链接结构。

一次遍历、同时拆两根链的方案

因此可以采用一种更优做法：遍历一次，每一步同时修改两个节点（一个奇数节点、一个偶数节点），这样就可以同时规避上面两个问题：

• 整个过程只新建两个虚拟节点（不复制数据节点），空间复杂度保持 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 app=leetcode id=328 lang=javascript * * [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.next，C++ 用odd->next = evenHead。

示例 1 的逐步推演

以1->2->3->4->5->NULL为例（采用 JS 版本指针语义）：

最终链表为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 下的对应文件。

延伸思考与变体

1. 空链表与单节点链表：两版代码开头均有if (!head || !head.next) return head;的边界保护，分别对应空链表与仅一个节点（无偶数节点）的情况，此时无需任何重排直接返回。
2. 节点数为偶数的情况：如1->2->3->4->NULL，第 2 轮后 odd=3、even=null 退出，odd.next = dummyHead2.next使3->2，得到1->3->2->4->NULL，重排正确。
3. 变体：按值分类而非按位分类：若题目改为「把值小于 x 的节点排在前面」，解法即为上文对照的 86. 分隔链表；若改为「链表节点按奇偶值分组」，则分组依据从「迭代位置」换成「节点值奇偶」，骨架代码几乎不变，只改判断条件。
4. 延伸：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