每天学习一点算法这个系列走到 2026/03/05我选了链表里非常经典的一道题——奇偶链表对应 LeetCode 上的第 328 题 Odd Even Linked List。这道题看起来简单但它是链表问题的分水岭能不能一次写对、能不能把边界情况说清楚、能不能跟面试官解释明白指针的每一步指向才是真正拉开差距的地方。今天这篇就当作一次完整的学习记录从题目拆解、思路推导、代码实现到变式扩展把我踩过的坑和验证过的经验全部写下来给后面刷链表题的同学做个参考。题目本身一句话就能说清给定一个单链表头节点 head把所有奇数索引节点排在一起偶数索引节点排在一起奇数部分在前、偶数部分在后同时保持各自的相对顺序不变。示例就是 1-2-3-4-5 变成 1-3-5-2-4。要求是原地完成时间复杂度 O(n)额外空间 O(1)。看起来平铺直叙但真正动手写的时候索引从哪开始数、到底改值还是改指针、循环怎么终止这几个点每一个都能卡住一大批人。我这次就把这些容易翻车的地方一一摊开讲清楚。1. 奇偶链表题目拆解3个容易被晃点的细节1.1 索引从1开始数组思维在这里是个坑我第一次做这道题的时候下意识用数组的下标习惯去理解以为头节点是索引 0那第二个节点是奇数节点。结果推演出来的答案刚好和题目要求反了。大家注意题目的索引是从 1 开始数的头节点是奇数节点第二个节点是偶数节点后面依次交替。这是这道题最容易踩的第一个坑。为什么题目要这样定义因为链表本身没有数组下标这样的天然属性它的节点顺序就是从头到尾的物理顺序。把第一个节点定义为奇数更多是约定俗成方便描述前一半奇数节点、后一半偶数节点。你只要记住一句话奇数节点链和偶数节点链是从第一个节点开始隔一个取一个分出来的而不是从什么 0 号位置开始。这里给出一个容易混淆的对照节点位置从1数节点索引奇偶性归属链你的直觉从0数第1个节点奇数奇数链偶数错第2个节点偶数偶数链奇数错第3个节点奇数奇数链偶数错第4个节点偶数偶数链奇数错这个表看着简单但你在纸上画图的时候特别容易按第二列走。我后来养成的习惯是碰到链表和索引奇偶挂钩的题目第一件事在草稿纸角落写上头奇把自己钉死在 1-based 上后面所有推演才不会歪。1.2 值交换是陷阱不是正解不少同学看到输出结果后第一反应是把奇数位置的节点值跟偶数位置的节点值交换一下不就行了比如 1-2-3-4-5交换成 1-3-5-2-4节点的值对了链表形态也变了。说实话OJ 平台这么干很可能能过因为判题只检查最终结果不看你怎么操作指针。但这里有两个客观问题。第一题目明确要求原地重排在链表语境下这个要求默认指的是调整节点之间的 next 指针关系而不是仅仅交换挂在节点上的值。你去面试时跟面试官说我把值交换了面试官第一反应就是你会不会链表——链表的精髓就是节点引用的重组值交换是数组的做法用在这里属于把链表当成数组用完全没有体现链表的特性。第二值交换在真实工程里有很大的隐性成本。链表节点本身可能不止一个 int 字段可能有 id、name、score 等一堆字段用值交换就得把整块节点数据全部交换代价完全不可控。而指针交换只是改 next 引用跟节点内部数据量无关。所以从数据结构设计角度来看标准的解法必须是拆链、重连而不是换值。我在实际练习中遇到过一种取巧写法把节点值收集到数组里重新按奇数位置、偶数位置排序后再写回节点。这种写法甚至不需要理解指针操作但额外空间是 O(n)不符合题目要求面试官一眼就能看出来你对原地的理解还停留在数组层面。所以别走捷径老老实实玩指针。1.3 一个5节点推演示例先建立目标形态为了后面思路好讲先做一个完整推演。假设输入链表是1 - 2 - 3 - 4 - 5按题意奇数索引节点是 1、3、5偶数索引节点是 2、4。目标链表是1 - 3 - 5 - 2 - 4细看这个目标状态你能发现两件事。第一奇数链内部是 1-3-5偶数链内部是 2-4它们的相对顺序都没有变变的只是原来 3 后面跟着 4现在 3 后面跟着 5。第二最终结果是奇数链整体接在偶数链前面中间靠 5 的 next 指向 2 来衔接而不是把 1 和 2 之间的关系整体打乱。这个目标形态一定要在动手写代码之前印在脑子里。后面所有双指针的 move 操作本质上都是奔着奇数链尾指向偶数链头这个终态去的。你没有目标就写代码很容易出现最后接不上的问题。2. 为什么双指针是标准答案思路推导与原理深挖2.1 最直觉的先拆后拼问题出在指针太多拿到这道题顺着题意想第一方案肯定是把奇数节点串成一条链把偶数节点串成另一条链最后奇数链尾接偶数链头。这个思路本身完全正确问题在于实现时你至少要维护四个指针奇数链头、奇数链尾、偶数链头、偶数链尾。每遍历一个节点你就要判断它是奇数还是偶数然后把它挂到对应链的尾部。这样写不是不行但代码会变得冗长。而且你每串一个节点都要注意从旧链表里摘下来这个动作——如果只是让奇数尾的 next 指向当前节点却忘了让当前节点的前驱指向新的后继旧链表还藕断丝连最终结果会乱成一锅粥。拆链法之所以容易翻车就是因为摘除节点和挂接节点这两个动作是分开的任何一个遗漏都会造成环或者丢节点。那有没有办法把MOVE 节点这一步做得更安全答案就是双指针同步推进它把摘除和挂接融合成两条指针的交替赋值不需要显式维护四个头尾指针代码量大幅缩水而且每一步都保证奇数链、偶数链各自的完整性。2.2 双指针的核心两个人同时分拣像拉链一样一路拉开标准解法维护两个指针odd 和 even。odd 指向当前已经串好的奇数链的尾部even 指向当前已经串好的偶数链的尾部。一开始 odd 指向头节点even 指向头节点的下一个节点。因为 head 就是奇数链的头所以奇数链头不用额外记录只需要把 even 的起点存下来记为 evenHead它是偶数链的头。循环里干的事情用大白话说就是odd 先把 even 后面那个节点拿走串到奇数链上odd 前进到新串的节点even 再把 odd 后面那个节点拿走串到偶数链上even 前进到新串的节点。两个人交替从原链的剩余部分取节点一轮取两个一个归奇数链一个归偶数链。你可以把它想象成一条拉链原链表是两条链纠缠在一起的初始状态odd 和 even 分别抓住一条从左往右一路拉开拉开的同时各自把侧边的齿重新排列好。这样一遍遍历走完奇数链和偶数链已经各自成型最后只需要把两段接起来。这个拉开的过程不需要像拆链法那样反复摘除节点因为 odd 和 even 的赋值交替之间节点本身已经被重新挂接完毕。为什么会安全关键在于这个循环步是接力式的。看两行关键代码奇数链摘节点odd.next even.nextodd odd.next 偶数链摘节点even.next odd.nexteven even.next。第一行把 even 后面的节点交给奇数链同时奇数链尾前进这时候 odd.next 恰好指向原本在 even 后面的后一个节点也就是下一个偶数节点。第二行正好把这个节点取走交给偶数链。这个配合天衣无缝因为 even 取走的节点永远等于 odd 刚刚看过但没拿走的那个节点。两个指针交替之间没有空隙也没有重复。2.3 循环终止条件的魔鬼藏在 even.next 里很多同学能理解双指针的想法但一到写 while 条件就卡住。标准写法是while (even ! null even.next ! null)为什么要同时判断 even 和 even.next这要从什么时候循环该停说起。因为每一轮循环要处理两个节点一个给奇数链一个给偶数链。如果剩下的节点数少于两个循环再继续就会出问题——要么 even 已经是 null你再访问 even.next 直接空指针要么 even 不是 null 但 even.next 是 null说明只剩一个节点而且是给奇数链用的那个偶数链没有新节点可取了。分两种情况看终止链表节点总数是偶数比如 4 个节点。循环处理完第 2 轮呢处理完两轮后 even 会推进到 null此时 even 为空循环终止。链表节点总数是奇数比如 5 个节点。循环处理完两轮后 even 会停在某个非空节点上但该节点的 next 已经是 null说明后面没有新节点供偶数链取此时 even.next 为空循环终止。如果只写 even ! null奇数个节点时会进入下一轮循环然后访问 even.next.next 之类的操作就会空指针如果只写 even.next ! null偶数个节点时会先判断 even 是不是 null 再访问 next同样可能先崩。所以一定要两个条件同时检查且顺序不能颠倒——先判断 even 不为空再判断 even.next 不为空这是 Java 里短路运算符的基本规则也是这段代码的安全底线。提示循环终止时odd 一定停在最后一个奇数节点上不管链表长度是奇数还是偶数。这个性质非常关键它保证了循环结束后执行 odd.next evenHead 能恰好把奇数链和偶数链接上不会出现奇数链尾还连着旧节点的情况。2.4 为什么空间复杂度必须是O(1)原地操作的真正含义题目要求的 O(1) 额外空间意味着你不能用 List、数组、栈、队列或者递归递归栈也算空间来辅助完成。所以所谓的收集节点到数组再重建根本不是正解空间复杂度直接 O(n) 不合格。那 O(1) 空间意味着什么它意味着你只能在原有的节点上改 next 指针不能 new 任何新节点。标准双指针方案全程只用 odd、even、evenHead 三个指针变量节点本身一个没创建、一个没删除完全符合原地要求。好多人觉得原地很难理解换个说法你手里只有一把螺丝刀不允许买新零件只能把现有零件的位置重新拧一遍。链表题里讲原地基本就是这个意思。时间复杂度 O(n) 也好证明每个节点在循环里最多被访问常数次只有头节点和尾节点被特殊处理一次整体是线性扫描。这两个复杂度指标对齐了算法才从能跑上升到合格。3. 动手写代码Java实现与逐步拆解3.1 完整代码先给一个能直接抄的版本public ListNode oddEvenList(ListNode head) { if (head null) { return null; } ListNode odd head; ListNode even head.next; ListNode evenHead even; while (even ! null even.next ! null) { odd.next even.next; odd odd.next; even.next odd.next; even even.next; } odd.next evenHead; return head; }这个版本是 LeetCode 上一行行推出来的标准解我把它原样保留在这里。有人习惯在开头加一句 if (head null || head.next null) return head; 提前处理单节点和双节点的情况这个防御性写法加不加都行。我个人的习惯是加了因为后面几行代码在读 head.next 的时候如果不是空链表head.next 可能是 null单节点这时 even 变成 null循环自然不执行最后 odd.next evenHead 会把单节点的 next 置为 null结果也正确。所以不加也完全能跑加了只是让边界更直观。3.2 逐行拆解每一行到底在干什么先看初始化那三行odd head奇数链初始只有头节点一个odd 是奇数链的尾。even head.next偶数链的初始节点是第二个节点even 是偶数链的尾。evenHead even把偶数链的头存下来不存的话循环结束后你找不到偶数链的入口。循环体四行核心逻辑我拆成四步来看第一步odd.next even.next。这一步动作是把当前偶数节点后面的那个节点接到奇数链尾部。例如链表 1-2-3-4-5odd 指向 1even 指向 2even.next 是 3执行后 1 的 next 变成 3链表瞬时状态变成 1-3-4-5 和 2-3 并存。第二步odd odd.next。odd 前进到新接上的奇数节点 3奇数链尾变成 3。第三步even.next odd.next。odd 现在指向 3odd.next 是 4这句话把 4 接到偶数链尾部 2 的后面执行后偶数链变成 2-4。第四步even even.next。even 前进到 4偶数链尾变成 4。一轮结束原链表里 1、2 已经被归类完成。第二轮开始时 odd 在 3even 在 4同样逻辑把 5 接到 3 后面6 接到 4 后面。整个过程就是两两分组地推进。循环结束后关键一行odd.next evenHead。把奇数链尾接到偶数链头。为什么这一行放到最后而不是每一轮都做因为如果每轮都让 odd.next 指向 evenHead那中间过程的奇链表就会长出一个多余的分支彻底混乱。必须等所有节点都归类完毕最后一个奇数节点才去连偶数链头。这一步是整个算法的收尾也是最容易漏的一行。3.3 边界情况逐项验证我写代码有个习惯写完先在脑子里过一遍边界用例再提交。这里把五种典型情况全部列出来输入链表预期输出代码执行路径nullnull开头 if 直接返回11even 为 null循环不执行odd.nextnull返回 11-21-2even 非空但 even.next 为 null循环不执行odd.nextevenHead 使 1 指向 2结果不变1-2-31-3-2循环执行一轮odd.next3odd3even.nextnullevennullodd.nextevenHead(2)1-2-3-41-3-2-4循环执行一轮后 even 走到 4even.nextnull 终止odd.nextevenHead(2)单节点和双节点这两个 case 特别容易被人忽略。很多人写完代码信心满满结果跑单节点直接空指针原因就是想当然地访问了 head.next.next。在链表的世界里每写一个 .next都要问自己一句这个节点确定不为 null 吗边界条件不是背出来的是每一次写代码时像这样一条条过出来的。3.4 复杂度证明为什么是O(n)和O(1)时间复杂度方面循环体内每轮处理两个节点一个给奇数链一个给偶数链指针向后移动两步。链表长度为 n 时循环最多执行 n/2 轮每轮是常数次操作所以总耗时 O(n)。即使链表只有一个节点也没有额外扫描。初始化操作和最后连接操作都是常数次不影响复杂度量级。空间复杂度方面全程只创建了三个局部指针变量 odd、even、evenHead无论链表多长额外占用都是固定大小。注意代码没有 new 任何 ListNode也没有递归调用所以额外空间严格 O(1)。这一点在面试中要能脱口而出因为有时候面试官不满足于你写对还要你把复杂度背后的理由说清楚。4. 变式与扩展学会一道题就要会一系列题4.1 变式一如果把偶数链放到奇数链前面呢这是最常见的追问方向。思路并不复杂标准解法是奇数链尾接偶数链头变式只是把连接顺序反过来偶数链尾接奇数链头。但实现的时候要注意一个细节奇数链的头部是 head偶数链的头部是 evenHead你需要把整个链表的头节点改为 evenHead。所以返回值不再是 head而是 evenHead并且要保证在偶数链走到末尾后把 even.next 赋值为 odd 所在的奇数链头。更稳妥的写法是加哨兵节点也就是 dummy 节点。用 dummy 头可以同时管理两条链的起点问题避免连接时找错头。我在做这类变式时一般会先画图把两条链的起点、终点标出来再确认最终 head 来自哪条链基本上就能绕开陷阱。面试官出这种变式考察的就是你能不能把一个套路迁移到相似场景。4.2 变式二分离奇偶节点后再各自反转这个变式把奇偶链表和链表反转两个考点叠在一起。先完成奇偶分离得到奇数链和偶数链然后对两条链分别用三指针就地反转最后按题意决定怎么拼接。举个典型场景奇数部分顺序反转、偶数部分保持不变或者反过来。链表反转的标准做法是三指针 pre、cur、next 循环每次把 cur.next 指向 pre然后三个指针整体前移。因为链表是单向的反转时必须提前保存下一个节点否则一改 next 就找不回后面的节点了。奇偶链表本身练习的是多指针同步移动反转练习的是指针方向逆转两者一结合正好把链表操作里最核心的两类动作都覆盖了。做这种组合题时我的建议是先分别实现、分别测试再合并。不要一上来就希望一步到位。单独跑通奇偶分离再单独跑通反转函数最后在 main 方法里手动构造几条测试链表验证拼接结果。模块化拆解是处理组合题的通用策略靠眼睛硬看代码很难发现问题。4.3 和排序、快慢指针等热点算法的关系搜索热词里经常能看到归并排序、堆排序、冒泡排序、快慢指针这些内容它们和奇偶链表在数据结构层面是相通的。我举个最直接的例子链表归并排序的第一步是用快慢指针找链表中点。快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这个快慢指针思想和奇偶链表的双指针思想是同一个谱系的——都是两个指针在同一条链上以不同节奏移动只是奇偶链表这里两个指针移动节奏严格同步处理的是相邻两个节点。排序类算法在链表上的实现核心难点之一也是交换节点和交换值的选择。数组里你可以毫无心理负担地 swap 两个下标的值链表里如果数据字段多swap 值依然可行但低效更符合链表气质的是调整指针。冒泡排序在链表上写起来之所以别扭就是因为它默认相邻元素交换值而链表相邻节点的指针关系需要额外维护。这跟奇偶链表里改值还是改指针的讨论完全是同一个坑。所以别把奇偶链表当成一道孤立的题。你把它吃透等于把链表双指针操作的基本功练了一遍。之后再去刷链表反转、链表排序、环形链表、寻找中点这些题会发现很多地方都在复用同一套在节点之间倒腾 next的手感。5. 常见报错与调试实录我踩过的那些坑5.1 空指针异常.next的连环雷最常见的报错是 NullPointerException而且几乎都发生在循环体内部。我见过最典型的错误写法是这样的while (even.next ! null) { odd.next even.next; odd odd.next; even.next odd.next; even even.next; }这段代码在链表长度是奇数时能跑长度是偶数时就会在某一轮访问 to even.next 时发现 even 已经是 null直接崩掉。另一种错误是 while 条件写对了但循环体里访问了 odd.next.next 这样的二级引用。比如有人在取下一个奇数节点时写成 odd.next even.next.next多取了一层完全打乱节奏。排查这类空指针我的办法是手工模拟一个 4 节点链表写一行代码就停下来看一眼当前所有指针分别指向谁。只要某一行的前提条件不满足比如 odd 或 even 是 null马上就能定位是哪一步推进过头了。纸上推演虽然慢但比在 IDE 里反复跑调试要快得多。5.2 死循环链表成环了死循环的典型症状是程序卡住不结束或者返回的结果链表里有环。原因通常是某个节点的 next 没有断干净。举个例子如果循环结束后你执行了 odd.next evenHead但循环过程中有一次 even.next 没有正确更新偶数链里某个节点可能还指向奇数链的某个节点形成环遍历链表时就会无限循环。还有一次我的代码在循环结束后忘记给偶数链的尾节点 next 置为 null。虽然标准解法里 even 推进到某个节点的 next 为 null 时自然断开但如果你改了循环条件或者步进方式就可能出现偶数链尾部还拖着一截奇数链的情况。这时候你输出链表会看到 1-3-2-4-3-2-4-3……典型的环状结构。排查死循环一个土办法是在主程序里加一个计数器比如遍历超过 10000 次就强制跳出并打印当前节点值。这样能快速确认是不是成环再用断点看环出现的位置。我刷链表题一直保留这个排查习惯它帮我省了很多时间。5.3 结果看起来没变或链表断开另一个高发问题是代码跑完结果单测却报错——要么链表根本没变要么链表中间断了一截。没变大概率是用了值交换但恰好用的是临时变量没写回去或者更常见的是你改的是节点的值还是节点的引用没搞清楚。比如你在方法里写了 ListNode cur head; 然后对 cur.next 赋值这是没问题的但如果你写的是 cur cur.next只是移动了局部变量不会影响原链表的任何连接关系。链表断开的典型场景是循环过程中把奇数链尾的 next 指到了某个正确节点但偶数链头的 next 没有同步修正结果两条链虽然都串好了最后拼接时却把某条链的尾节点指向了 null 或者旧节点。解决方案还是回到 2.3 节说的那个性质循环结束时 odd 必然停在最后一个奇数节点把这个信息利用好连接动作就不会做错。5.4 一个实用的调试技巧先打印链表写链表题必须先有一个顺手的链表打印函数。我在本地刷题时是这样写的public static void printList(ListNode head) { ListNode cur head; int count 0; while (cur ! null count 20) { System.out.print(cur.val - ); cur cur.next; count; } System.out.println(null); }count 上限 20 是防止成环时无限打印打印二十个节点足够看出大部分问题。每完成一个阶段就在代码里插一行 printList(head)能直观看到每一轮之后链表长什么样。比如第一次执行完循环打印看看是不是 1-3-5 和 2-4 都各自就位了再执行 odd.next evenHead打印最终结果。这样一步步验证比单测只告诉我结果错误要直观得多。注意本地调试时千万别在原题环境里疯狂打印LeetCode 这类 OJ 对标准输出没有限制但刷题习惯最好还是靠断点和单测来定位问题。打印只适合本地快速确认结构不要形成依赖。结尾一些刷链表题的个人体会这道奇偶链表题我前前后后大概写了四五遍每次重写都有新体会。最深的感受是链表题的难点从来不在算法思想而在对指针状态的掌控力。双指针的思路五分钟就能讲明白但能不能保证每一个边界条件都正确、每一步指针移动都有明确的含义才是区分熟练和老练的关键。给准备面试和正在刷题的同学两个建议。第一拿到链表题先在纸上画图把节点、指针、目标终态全部画出来再开始写代码画图的过程能提前暴露几乎所有边界问题。第二多想想这个指针为什么这么移这行代码在什么条件下会崩溃不要满足于把标准答案背下来。奇偶链表只是入口后面还有反转链表、合并链表、环形链表、排序链表等着你但基本功都是一样的——理解 next 指针的一举一动。希望这篇记录能帮你在链表这条路上少走几步弯路。