题目

标题和出处

标题：奇偶链表

出处：328. 奇偶链表

难度

4 级

题目描述

要求

给你一个链表的头结点 ，把所有的奇数下标结点排在前面的组，把所有的偶数下标结点排在后面的组，返回重新排列后的链表。

链表的第一个结点视为奇数结点，第二个结点视为偶数结点，以此类推。

在奇数组和偶数组内部的结点的相对顺序应和输入保持一致。

要求空间复杂度为 %7D#card=math&code=%5Ctexttt%7BO%281%29%7D&id=aIbf6)，时间复杂度为 %7D#card=math&code=%5Ctexttt%7BO%28n%29%7D&id=WhkCd)。

示例

示例 1：

输入：
输出：

示例 2：

输入：
输出：

数据范围

• 链表中结点数目为
• 
• 

解法

思路和算法

如果链表为空，则直接返回空链表即可。当链表不为空时，链表中的每个结点都是奇数结点或偶数结点，且相邻结点的奇偶性不同，因此可以将原始链表分离成奇数链表和偶数链表，然后将偶数链表拼接在奇数链表之后，即完成了链表的重新排列。

原始链表的头结点 也是奇数链表的头结点和结果链表的头结点， 的后一个结点是偶数链表的头结点，即 是偶数链表的头结点。

维护两个指针 和 分别指向奇数结点和偶数结点，初始时 ，。每一步操作更新 和 指向的结点，使得 和 分别指向下一个奇数结点和下一个偶数结点，在更新当前奇偶结点的 的指向之后，将 和 分别向后移动一步，到下一个奇数结点和偶数结点。

具体做法为依次执行以下 步操作：

1. 将 指向 ，更新后的 指向下一个奇数结点；
2. 令 ，将 移动到下一个奇数结点；
3. 将 指向 ，更新后的 指向下一个偶数结点；
4. 令 ，将 移动到下一个偶数结点。

上述 步操作完成一个奇数结点和一个偶数结点的分离，并将奇数结点和偶数结点移动到下一个奇数结点和下一个偶数结点。重复上述操作，直到全部结点分离完毕。

全部结点分离完毕时， 指向最后一个奇数结点， 指向 或者最后一个偶数结点，取决于链表长度（结点数）是奇数或者偶数。

全部结点分离完毕之后，由于 指向最后一个奇数结点，因此将 拼接在 之后，即完成了链表的重新排列。结果链表的头结点是 。

下图为示例 1 的重新排列链表的过程。奇数结点和偶数结点分别在两行，绿色和蓝色分别表示 和 指向的结点。

代码

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode odd = head, even = head.next, evenHead = head.next;
        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;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=cTaVp)，其中 是链表的长度。需要遍历链表一次，对每个结点分离和合并操作都是 #card=math&code=O%281%29&id=uFvZw) 的时间。
• 空间复杂度：#card=math&code=O%281%29&id=xljUw)。