【deco】deco的中等难度题(八十六)

大家好，今天继续讲解 deco 的中等难度题。

1. 今天讲解第八十六题：分隔列表。

2. 来看一下题目，给你一个列表的头结点 head 和一个特定的值 x，请你对列表进行分隔，使得所有小于 x 的节点都出现在小于等于 x 的节点之前，保留两个分区中每个节点的初始相对位置，比如这个：一、四、三、二、五，x 等于 3，小于 3 的一、二、二保持顺序，大于 3 的四、三、五保持顺序，就是一、二、二、四、三、五。一、二是二，有一代前、二代后，列表中节点的数目在范围在零到两百之间，就说明这个列表可能为空，先判断为空的 not，如果为空直接返回一个空就可以了。

3. 如果被控怎么处理？因为要保持一个相对顺序，而且要把小于 x 的和大于等于 x 的放分开，怎么办？可以用两个例子来保存，把小于 x 的放到前第一个例子的，把大于 x 的放到第二个历史当中，而且这个列表从前往后循环，往两个历史中放就能保持相对顺序，就做一下。首先定义两个表 l1、l2，初始都为空，然后来循环这个列表，一个 tamp 指向头，如果 tamp 的 value 小于 x，那么就 append 到 l1 中，如果它大于等于就是把它 append 进 l2 当中，然后定一个新的 list 等于 l1 加 l2 拼起来，然后获取它这个长度。这边漏了一点，列表循环 tamp 要每次要等于 tamp 的 next 才能一直访问下一个节点，把这个列表循环完，n 等于 list 的 len，然后重新梳理这个列表，循环零到 n-2，list 的 i next 指向下一个节点，list 的 i+1，list 负 1 的 next 最后一个节点 next 就为空了，然后返回 list 的零节点就是它的新列表的头了。

4. 测试一下，这是通过，提交一下，提交通过，这道题要求把小于 x 节点放到大于等于 x 节点之后，同时保留它的初始位置，可以便利列表，便利这个列表大于小于 x 放到一个历史当中，大于等于 x 放到另一个历史当中，这样它的相对顺序就保证了。同时把小于 x 和大于等于 x 分成两个列表，再把这两个列表加在一起，叠加在一起，然后把它梳理组成一个新的列表返回到头就可以了。

今天的题目讲完了，谢谢大家。