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

  |  

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

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的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 链表,相对位置不变

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

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

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

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

提示:

1
2
3
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)$ 额外空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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)$ 空间

1
2
3
4
5
6
7
8
9
10
11
12
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]);
}
}
}

Share