奇数位置元素排在偶数位置元素之前

摘要: 线性结构上的一种常见操作

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们来看一个在线性结构上非常常见的操作，就是将奇数位置的元素排在偶数位置的元素之前。

首先我们考虑最简单的情况，如果这个线性结构是数组，例如 [1, 2, 3, 4]，奇数位置元素为 1, 3；偶数位置元素为 2, 4。将该奇数位置元素放到偶数位置元素之前，也就是将 1, 3 放到 2, 4 前面，[1, 3, 4, 2] 是一种可能得结果。

在此基础上，有时还会额外要求保持相对顺序，还是以 [1, 2, 3, 4] 为例子，此时 [1, 3, 4, 2] 就不行了，因为要保持相对顺序，结果只能是 [1, 3, 2, 4]。题目 932. 漂亮数组 的算法中的其中一步用到了这个操作。

同样的需求，在链表上也是有的，只是实现上稍微有一些区别。例如 1 -> 2 -> 3 -> 4，将奇数位置元素放到偶数位置元素，同时需要保持相对顺序，结果为 1 -> 3 -> 2 -> 4。题目 328. 奇偶链表 就是实现的这个操作。

下面我们解决这两个问题，其中 932 题涉及到的分治算法还有点难度，下一篇文章我们再拆解，本文仅仅把我们关心的操作实现一下，后续在拆解 932 的时候直接用即可。

$1 链表,相对位置不变

• 328. 奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

提示:

n ==  链表中的节点数
0 <= n <= 1e4
-1e6 <= Node.val <= 1e6

示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

代码 (C++)

$O(N)$ 时间 $O(1)$ 额外空间

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head) return nullptr;
        if(!head -> next || !head -> next -> next) return head;
        ListNode *iter_odd = head, *iter_even = head -> next, *head_even = head -> next;
        int odd = 1;
        ListNode *iter = head -> next -> next;
        iter_odd -> next = nullptr;
        iter_even -> next = nullptr;
        while(iter)
        {
            if(odd == 1)
            {
                iter_odd -> next = iter;
                iter = iter -> next;
                iter_odd = iter_odd -> next;
                iter_odd -> next = nullptr;
                odd ^= 1;
            }
            else
            {
                iter_even -> next = iter;
                iter = iter -> next;
                iter_even = iter_even -> next;
                iter_even -> next = nullptr;
                odd ^= 1;
            }
        }
        iter_odd -> next = head_even;
        return head;
    }
};

---

$2 数组,相对位置不变

932. 漂亮数组

方法1：用辅助数组 $O(N)$ 时间 $O(N)$ 空间

方法2：用类似冒泡排序的思想 $O(N^{2})$ 时间 $O(1)$ 空间

void reOrderArray(vector<int> &nums) 
{
    int n = nums.size();
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n - i - 1; ++j)
        {
            if ((nums[j] & 1) == 0 && ((nums[j + 1] & 1) == 1))
                swap(nums[j], nums[j + 1]);
        }
    }
}

---