[LeetCode] Odd Even Linked List 奇偶链表

时间:2022-09-26 08:47:37

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input. 
The first node is considered odd, the second node even and so on ...

Credits:
Special thanks to @aadarshjajodia for adding this problem and creating all test cases.

这道题给了我们一个链表,让我们分开奇偶节点,所有奇节点在前,偶节点在后。我们可以使用两个指针来做,pre指向奇节点,cur指向偶节点,然后把偶节点cur后面的那个奇节点提前到pre的后面,然后pre和cur各自前进一步,此时cur又指向偶节点,pre指向当前奇节点的末尾,以此类推直至把所有的偶节点都提前了即可,参见代码如下:

解法一:

class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *pre = head, *cur = head->next;
while (cur && cur->next) {
ListNode *tmp = pre->next;
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = tmp;
cur = cur->next;
pre = pre->next;
}
return head;
}
};

还有一种解法,用两个奇偶指针分别指向奇偶节点的起始位置,另外需要一个单独的指针even_head来保存偶节点的起点位置,然后把奇节点的指向偶节点的下一个(一定是奇节点),此奇节点后移一步,再把偶节点指向下一个奇节点的下一个(一定是偶节点),此偶节点后移一步,以此类推直至末尾,此时把分开的偶节点的链表连在奇节点的链表后即可,参见代码如下;

解法二:

class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *odd = head, *even = head->next, *even_head = even;
while (even && even->next) {
odd = odd->next = even->next;
even = even->next = odd->next;
}
odd->next = even_head;
return head;
}
};

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Odd Even Linked List 奇偶链表的更多相关文章

  1. 328 Odd Even Linked List 奇偶链表

    Given a singly linked list, group all odd nodes together followed by the even nodes. Please note her ...

  2. [LeetCode] 328. Odd Even Linked List ☆☆☆(奇偶节点分别放一起)

    每天一算:Odd Even Linked List 描述 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起.请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性. 请尝 ...

  3. 【LeetCode】Design Linked List(设计链表)

    这道题是LeetCode里的第707到题.这是在学习链表时碰见的. 题目要求: 设计链表的实现.您可以选择使用单链表或双链表.单链表中的节点应该具有两个属性:val 和 next.val 是当前节点的 ...

  4. [LeetCode] 206. Reverse Linked List 反向链表

    Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. ...

  5. Leetcode Odd Even Linked List

    Given a singly linked list, group all odd nodes together followed by the even nodes. Please note her ...

  6. LeetCode 206. Reverse Linked List倒置链表 C++

    Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4-&gt ...

  7. [LeetCode] 206. Reverse Linked List ☆(反转链表)

    Reverse Linked List 描述 反转一个单链表. 示例: 输入: 1->2->3->4->5->NULL    输出: 5->4->3-> ...

  8. LeetCode 707. Design Linked List (设计链表)

    题目标签:Linked List 题目让我们自己设计一个 linked list,可以是单向和双向的.这里选的是单向,题目并不是很难,但要考虑到所有的情况,具体看code. Java Solution ...

  9. Leetcode 203 Remove Linked List Elements 链表

    去掉链表中相应的元素值 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next ...

随机推荐

  1. constraint更新表列约束默认值

    --更新约束 alter TABLE [dbo].[Sk_Recruit] drop constraint DF_Sk_Recruit_lastcommenttime go   alter TABLE ...

  2. IT安全的本质

    (1)信任:服务端信任客户端的请求参数. (2)可控:客户端的请求参数可以被控制,任意修改. 服务端信任+客户端可控 =不安全. 服务端信任+客户端不可控=安全. 服务端不信任+客户端可控=安全. 服 ...

  3. Ubuntu 15.04 安装 Nvidia Quadro系列显卡驱动

    在这之前,我用的Ubuntu都是系统自带的驱动, 由于分辨率没有任何问题, 所以一直没有安装Nvidia官方的驱动; 近期更新到 15.04 之后, 在播放avi 格式的常规视频时却出现闪烁的现象, ...

  4. Apache代理和反向代理

    服务器上安装了多个服务,包括apache的80端口,以及tomcat的8080和8090,为了访问使用方便,尝试了代理和反向代理.下面是部分配置以备参考: NameVirtualHost *:80 & ...

  5. Python: 作图

    在python中实现数据的可视化,也即作图,一般是依赖matplotlib宏包实现的.但常见的代码中都是加载pylab,是不是这里写错了呀?其实pylib只是matplotlib的一个模块,只是被做成 ...

  6. npm ERR! code ENOENT

    npm ERR! path F:\VsCodeWorkspace\labWeb\front\LabWebAdminFrontEnd\node_modules\core-jsnpm ERR! code ...

  7. QTP 自动化测试桌面程序--笔记(下拉选择、右键菜单、在控件仓库中查找对应的控件)

    0 在收集窗口控件信息时-最好将可输入的文字去掉,不然控件的名称按输入的文字标记 1 编辑时录制脚本-默认按当前显示的填入的数据标记控件 可以使用 tool-spy-查看控件的x,y 坐标,按坐标在学 ...

  8. Git学习一:基本用法

    git config:配置相关信息 git clone:复制仓库 git init:初始化仓库 git add:添加更新内容到索引中 git diff:比较内容 git status:获取当前项目状况 ...

  9. 判断一个String中是否有指定字符或字符串

    String test=“qwer”; if (test.contains("个we")){ do; }

  10. hadoop之 reduce个数控制

    1.参数变更1.x 参数名                                                         2.x 参数名 mapred.tasktracker.red ...