【数据结构和算法】奇偶链表

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

---

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一：分离节点后合并

三、代码

3.1 方法一：分离节点后合并

四、复杂度分析

4.1 方法一：分离节点后合并

---

前言

这是力扣的 328 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。

慢慢开始链表的模块了，这道题是一道非常好的队列的例题，很有代表性。

---

一、题目描述

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

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

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

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

示例 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]

提示:

• n ==  链表中的节点数
• 0 <= n <= 104
• -106 <= Node.val <= 106

---

二、题解

2.1 方法一：分离节点后合并

思路与算法：

如果链表为空，则直接返回链表。

对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。

原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点，head 的后一个节点是偶数链表的头节点。令 evenHead = head.next，则 evenHead 是偶数链表的头节点。

维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。

• 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然后令 odd = odd.next，此时 odd 变成 even 的后一个节点。
• 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然后令 even = even.next，此时 even 变成 odd 的后一个节点。

在上述操作之后，即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点）。

最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然是 head。

如下图所示：

---

三、代码

3.1 方法一：分离节点后合并

Java版本：

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

C++版本：

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

Python版本：

class Solution:def oddEvenList(self, head: ListNode) -> ListNode:if not head:return headevenHead = head.nextodd, even = head, evenHeadwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = evenHeadreturn head

Go版本：

func oddEvenList(head *ListNode) *ListNode {if head == nil {return head}evenHead := head.Nextodd := headeven := evenHeadfor even != nil && even.Next != nil {odd.Next = even.Nextodd = odd.Nexteven.Next = odd.Nexteven = even.Next}odd.Next = evenHeadreturn head
}

---

四、复杂度分析

4.1 方法一：分离节点后合并

• 时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表中的每个节点，并更新指针。
• 空间复杂度：O(1)。只需要维护有限的指针。

---