LeetCode 328. 奇偶链表

约 4 分钟
文章信息 21 个分类 1 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 LeetCode 75 腾讯 字节 阿里 华为 微软 亚马逊 美团 小米 百度 快手 滴滴 携程 旷视 猿辅导
标签
链表

题目描述

✅ 328. 奇偶链表

image-20260928195806257

image-20260928195806258

题意分析

按节点在原链表中的位置重排：先连接原第 1、3、5… 个节点，再连接原第 2、4、6… 个节点，并保持每组内部的原有顺序。位置从 1 开始计数，节点值的奇偶不影响分组。

需要调整原有节点的连接并返回新链表，要求线性时间和常数额外空间。第一个节点始终属于奇数组并保持在最前面；空链表以及仅有一两个节点的链表都不需要实际重排。

解法：原地拆分奇偶位置链表

核心思路

[!blue]

把原链表逐步拆成奇数位置链和偶数位置链，最后把两条链连接起来。odd、even 分别指向目前已经处理到的奇数节点和偶数节点；初始指向原第一、第二个节点。同时用固定指针 evenHead 保存偶数链的入口，避免游标移动或原连接变化后找不到它。

若 even 后面还存在节点，那么 even.next 就是下一个奇数位置节点。先令 odd.next = even.next，把它接到奇数链尾，再推进 odd。新 odd 原来的后继就是下一个偶数位置节点，因此接着令 even.next = odd.next，再推进 even。四步按依赖关系执行，才能在覆盖连接之前正确取得未处理后继。

每次都从原链表剩余部分依次取出下一组节点，分别接到对应链尾，不改变组内先后顺序，因此得到的是稳定分组。两条链在处理途中不必每次完全断开，只要游标和固定入口始终能找到各自部分即可。

循环在偶数游标为空，或它后面已无奇数节点时结束。此时奇数链已完整，将 odd.next 改为 evenHead，就把完整偶数链接到末尾。偶数链尾已经为空，拼接后不会形成环；不能改用已被重写的 head.next 或已移动到尾部的 even 作为入口。

解题步骤

  1. 空链表直接返回；否则初始化 odd = head、even = head.next，保存 evenHead = even。
  2. 只要 even 和 even.next 均非空，就把 even.next 接到奇数链尾，并向前移动 odd。
  3. 用新 odd.next 连接下一个偶数节点，并向前移动 even。
  4. 重复处理，直到没有完整的下一组节点；令 odd.next = evenHead 拼接两部分。
  5. 返回原头节点 head。

代码实现

class Solution {
    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;
    }
}

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    odd := head
    even := head.Next
    // 提前保存偶数链头，游标移动到尾部后仍能找到完整偶数链。
    evenHead := even
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    // 奇数链处理完后接上完整偶数链，不只是接当前偶数游标。
    odd.Next = evenHead
    return head
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点只经过常数次访问和重连。
  • 空间复杂度：$O(1)$，只保存奇数游标、偶数游标和偶数链入口，不创建额外节点。

关键点总结

[!green]

  • 分组依据是原始位置，沿原后继交替推进，自然保持两组内部顺序。
  • evenHead 是固定入口，even 是移动游标，二者职责不能混用。
  • 先推进奇数链，再利用新奇数节点的后继推进偶数链。
  • 最后只改奇数尾的一条连接，就能接回完整偶数链。

易错点总结

[!yellow]

  • 根据节点值判断奇偶，改变了题目按位置分组的要求。
  • 未判空就读取 head.next，或只检查 even 不检查其后继，都会导致空节点访问。
  • 没有提前保存偶数入口，循环改写 head.next 后无法用它找回原第二个节点。
  • 最后接到 even 而不是 evenHead，只能接到偶数链尾或空节点，会遗漏前面的偶数节点。
  • 不按依赖顺序执行四条赋值，可能读取已覆盖的后继，导致丢失节点或形成环。

相似题目

题目 难度 关联与区别
86. 分隔链表 中等 同样稳定分成两条链后连接，本题按位置奇偶，原题按值与阈值比较。
143. 重排链表 中等 同样先拆分再重连链表，但原题按首尾交替，本题按原下标奇偶分组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/54921733
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！