1.链表划分
思路一:可以把链表当作一副牌一样,用指针p遍历,不断地把比指定值x小的几点不断地插到前面比指定值小的的牌的最后边,如果遍历带大于等于指定值x的节点就不用管。我们指定一个Boolean值变量flag用来记录p左边是否有大于等于指定值的节点。定义pre为p前驱节点,T为已遍历而且比x小的最有节点;
一共可能会遇见三种情况(x=3)
情况一:当p.val>=x,那么pre和p都向右移动就行.然后flag设为false,因为p此时已经移动到大于等于x节点
情况二,p左边没有比x 大的节点(flag==true),而且p.val<x,那么
p,pre,T,都向右移动一位。
情况三,p左边有比x大的节点(flag==false),那么把p调转到T的后面去,然后更新所有节点。
实现代码:
思路二
实现代码:
扩展问题:
2. 链表洗牌
示例代码: