【LeetCode75】第三十题 奇偶链表

目录

 

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目给我们一个链表，让我们把奇索引和偶索引的节点区分开来 ，参考示例给出的图我们应该就能很清晰地知道题目是什么意思了。

每次做链表题，我的第一反应都是先把链表的每个节点都先存起来再做处理。

不过这道题有给出限制，O（1）的额外空间和O（n）的时间复杂度，就是我们不能拿额外的容器来存，并且需要只遍历链表一次就得出答案。

我们可以额外建立两条链表，然后遍历链表，拿一个索引值来记录节点是奇还是偶，如果是奇数，那么我们就把该节点转移到奇数的那条链表里，反之就转移到偶数的那条链表里，最后把原始链表 瓜分完之后再把奇偶链表连接起来就好啦。

 

代码：

class Solution {
public:ListNode* oddEvenList(ListNode* head) {if(head==nullptr || head->next==nullptr) return head;   //长度小于等于1的特殊情况直接返回ListNode* odd=head;ListNode* todd=head;ListNode* even=head->next;ListNode* teven=head->next;int index=1;head=teven->next;while(head!=nullptr){if(index%2==0){ //如果是偶节点teven->next=head;   //让偶接收teven=teven->next;}else{  //反之是奇节点todd->next=head;    //让奇接收todd=todd->next;}index++;head=head->next;}teven->next=nullptr;    //偶后面是空指针todd->next=even;        //奇后面是偶的开头return odd;}
};