每天一算:Odd Even Linked List

LeetCode上第328号问题:Odd Even Linked List

题目

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

解题思路

这道题给了我们一个链表,让我们分开奇偶节点,所有奇节点在前,偶节点在后。

  • 设定两个虚拟节点,dummyHead1用来保存奇节点,dummyHead2来保存偶节点;
  • 遍历整个原始链表,将奇节点放于dummyHead1中,其余的放置在dummyHead2
  • 遍历结束后,将dummyHead2插入到dummyHead1后面

动画演示

动画演示GIF有点大,请稍微等待一下加载显示^_^

参考代码

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

原文发布于微信公众号 - 五分钟学算法(blgczzz)

原文发表时间:2018-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数,例如: >>> int(3.2) 3 >>> int(1/3) 0 其实,int是Python内置类型之一,之所以能...

3097
来自专栏章鱼的慢慢技术路

解密回文——栈

1513
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1493
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

851
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1653
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

57110
来自专栏Bingo的深度学习杂货店

Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element ...

2826
来自专栏架构之路

一条直线上N个线段所覆盖的总长度

转自http://blog.csdn.net/bxyill/article/details/8962832 问题描述: 现有一直线,从原点到无穷大。 这条直线上...

3765
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

3178
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

2027

扫码关注云+社区

领取腾讯云代金券