P104. 链表划分

leetcode 86 lintcode 96 链表 双指针 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个单链表和一个数字,你要把小于这个数字的节点都移到链表前面,大于等于这个数字的节点都移到链表后面。并且在较小和较大的这两堆节点中,节点之间的相对顺序保持不变。

比如说,给你的单链表是:

0 -> 4 -> 2 -> 1 -> 8 -> 1

给你的数字是 2。小于 2 的节点有 0/1/1 共 3 个,大于等于 2 的节点有 4/2/8 共 3 个。因此重新划分后得到的链表是:

0 -> 1 -> 1 -> 4 -> 2 -> 8

可以看到,较小的那一堆 0/1/1 三个节点保持了在原链表中的相对顺序,较大的那一堆 4/2/8 三个节点也保持了在原链表中的相对顺序。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。