每天一算:Partition List

LeetCode上第86号问题:Partition List

题目

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5

解题思路

这道题要求我们划分链表,把所有小于给定值的节点都移到前面,大于该值的节点顺序不变,相当于一个局部排序的问题。

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

动画演示

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

动画演示

参考代码

执行结果

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏http://www.cnblogs.com

生成器&迭代器

一.生成器 在介绍生成器表达式之前,先看下列表表达式: 1 >>> l = [i for i in range(50) if i % 2] #生成...

351100
来自专栏机器学习实践二三事

python基础----map和reduce

map和reduce Map简单来说就是:一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素进行指定的操作 Reduce简单来说就是:对一个列表的...

20960
来自专栏IT可乐

深入理解计算机系统(2.5)------C语言中的有符号数和无符号数以及扩展和截断数字

  上一篇博客我们讲解了计算机中整数的表示,包括无符号编码和补码编码,以及它们之间的互相转换,个人觉得那是非常重要的知识要点。这篇博客我们将介绍C语言中的有符号...

29280
来自专栏编程微刊

从列表中或数组中随机抽取固定数量的元素组成新的数组或列表

2:jQuery版本 那么jQuery中怎么随机选出固定数组数组[1, 2, 3, 4, 5, 6, 7, 8, 9]中的三个元素,并构造成新数组的?

10710
来自专栏书山有路勤为径

栈与队列基础知识

栈,是先进后出的线性表,标准STL的栈包括如下5种操作,设栈S: 1.取出栈顶元素:S.top(); 2.判断栈是否为空:S.empty(); 3.将元素...

9220
来自专栏赵俊的Java专栏

两数之和

22630
来自专栏锦小年的博客

Python数据分析(3)-numpy中nd数组的创建

1、ndarray的内存结构 和其他的库一样,每个库都可能有自己独特的数据结构,例如OpenCV,numpy库的多维数组叫做ndarray( N dimensi...

23580
来自专栏机器学习从入门到成神

字符串面试题(二)— 间隔字符串逆序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

20730
来自专栏面朝大海春暖花开

入住腾讯云+社区

对于的github基础代码https://github.com/chywx/JavaSE

24610
来自专栏专注研发

交换排序—冒泡排序(Bubble Sort)

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们...

12920

扫码关注云+社区

领取腾讯云代金券