【数据结构和算法】奇偶链表
其他系列文章导航
文章目录
前言
这是力扣的 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 head
evenHead = head.next
odd, even = head, evenHead
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = evenHead
return headGo版本：
func oddEvenList(head *ListNode) *ListNode {
if head == nil {
return head
}
evenHead := head.Next
odd := head
even := evenHead
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = evenHead
return head
}
四、复杂度分析
4.1 方法一：分离节点后合并
- 时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表中的每个节点，并更新指针。
- 空间复杂度：O(1)。只需要维护有限的指针。
原文地址：https://blog.csdn.net/kologin/article/details/135616984
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！