「每日LeetCode」2020年11月13日
本文最后更新于:2023年3月19日 晚上
Lt328. 奇偶链表
328. 奇偶链表
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
1 |
|
示例 2:
1 |
|
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
思路
额外数组+遍历两次
空间复杂度 O(N),时间复杂度 O(2*nodes)。
遍历一次,存储奇数偶数节点的值到奇数偶数数组中。再遍历一次,修改链表节点的值。
遍历一次+无额外空间
设置一个 o 指向奇数节点,e 指向偶数节点,temp 指向第一个偶数节点用于记录第偶数节点链表。遍历一次链表:
- 先将奇数节点的 next 指向偶数节点的 next 即下一个奇数节点,就将两个奇数节点连接到了一起,再令 o 指向 o.next。
- 然后将 e 的 next 指向 o 的 next,即将该节点连接上了第二个偶数节点,再令 e 指向 e.next。
循环以上过程,遍历完成以后,分别形成了奇数和偶数的两条链表。将奇数节点链表的最后一个指向 temp,即连接上奇数和偶数链表。
解答
额外数组+遍历两次
1 |
|
遍历一次+无额外空间
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!