0328. Odd Even Linked List

题目信息

题号:

0328

难度:

Medium

主题:

单链表、位置奇偶、稳定重排、原地链接

原题:

LeetCode 0328

重点:

奇偶指节点的一基位置而非节点值、两组内部相对顺序保持、返回重排后的头节点

题目重述

给定单链表头节点 head,按照节点在原链表中的一基位置重新连接节点:位置为 1, 3, 5, ... 的节点依次放在前面,位置为 2, 4, 6, ... 的节点依次接在后面。

奇数位置组和偶数位置组内部都必须保持原有相对顺序。节点数位于 [0, 10^4],节点值位于 [-10^6, 10^6];分组依据是位置编号,与节点值本身的奇偶无关。题目要求 O(n) 时间和 O(1) 额外空间,并返回重排后的头节点。

自建示例

节点值的奇偶与分组无关:

输入:head = [8, 3, 6, 1]
输出:[8, 6, 3, 1]
解释:原位置 1、3 的节点值为 8、6,先按原顺序连接;位置 2、4 的 3、1 随后连接。

空链表:

输入:head = []
输出:[]
解释:没有节点需要重新连接,返回空链表。

同时维护两条稳定链

odd 指向当前奇数位置链的尾部,even 指向当前偶数位置链的尾部,另存 evenHead 作为偶数链的起点。每轮把 even 后面的节点接到奇数链尾部,再把新奇数节点后面的节点接到偶数链尾部;因为节点总是按原顺序取出,两条链内部都保持稳定。

循环结束时,奇数链比偶数链多一个或刚好一样长,even 或 even->next 为空。把奇数链尾接到 evenHead,即可得到完整结果;整个过程只改指针,不创建节点。

C++ 实现

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = 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;
    }
};

代码分析

odd 和 even 的移动分别跳过一个节点,因此每个原节点只被重新接线有限次;奇偶指的是原位置而不是值,代码没有读取节点值。空链表和单节点链表直接返回,避免访问空指针。时间复杂度为 O(n),额外空间为 O(1)。