如何将一个链表按指定数字进行分区？
站长
· 阅读数 14
前言
本文介绍如何将一个链表按指定模式进行分区，例如分为小、中、大3部分，然后再把几个部分给串起来。
正文
现在有这样一个面试题目：
将单向链表按某值划分左边小、中间相等、右边大的形式，然后再把三部分再次串起来。
例如：现在有个单链表7->4->3->1->0，按数字3进行划分，划分为3组，小于3的为一组、等于3的为一组、大于3的为一组，然后再把3组节点给串联起来，如下图所示。
思路解析
首先看看不借助其他容器、只使用有限几个变量实现题目的功能的思路：
用到哪几个变量呢？
- 小于指定数字的头结点
- 小于指定数字的尾结点
- 等于指定数字的头结点
- 等于指定数字的尾结点
- 大于指定数字的头结点
- 大于指定数字的尾结点
有了这几个变量之后该怎么做呢？
- 遍历单链表
- 如果结点值小于指定数组，判断小于指定数字的头结点和尾结点是否为空，如果为空的话，先进行初始化，初始化值为刚刚遍历的节点值(同样等于、大于也是一样的操作)
- 在遍历的过程中，如果上面六个变量没有赋值则进行赋值，如果已经存在了，则把新节点拼接在后面，并且把上面对应的尾结点变量给重新赋值
上面这个示例的节点个数太少，现在来换个链表看下：
假如有个链表：4->5->2->6->1->4->4->0->7，按4进行划分，划分的结果为：
- 小于
4的区域：2->1->0，其中2为头结点，0为尾结点 - 等于
4的区域：4->4->4，其中4为头结点，4为尾结点 - 大于
4的区域：5->6->7，其中5为头结点，7为尾结点
3个区域头尾串起来之后就是：2->1->0->4->4->4->5->6->7。
需要注意的是，虽然是划分了3个区域，但是可能3个区域的某个区域里没有节点，需要考虑边界问题。
代码实现
根据上面的思路分析，来看一下具体的代码是怎么样的吧：
public static Node listPartition2(Node head, int pivot) {
// 小于pivot区域的头结点
Node sH = null;
// 小于pivot区域的尾结点
Node sT = null;
// 等于pivot区域的头结点
Node eH = null;
// 等于pivot区域的尾结点
Node eT = null;
// 大于pivot区域的头结点
Node mH = null;
// 大于pivot区域的尾结点
Node mT = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = null;
// 小于的区域
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
// 等于的区域
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
// 大于的区域
if (mH == null) {
mH = head;
mT = head;
} else {
mT.next = head;
mT = head;
}
}
head = next;
}
// 小于区域的尾节点，连等于区域的头节点，等于区域的尾节点连大于区域的头结点
// 如果有小于区域
if (sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// 下一步，一定是需要用eT 去接 大于区域的头节点
// 有等于区域，eT -> 等于区域的尾结点
// 无等于区域，eT -> 小于区域的尾结点
// eT 尽量不为空的尾巴节点
if (eT != null) {
eT.next = mH;
}
return sH != null ? sH : (eH != null ? eH : mH);
}
总结
本文介绍如何将一个链表按指定模式进行分区，例如分为小、中、大3部分，然后再把几个部分给串起来，本次的解题方法需要点编码技巧，除了这种方式外，还可以使用数组分区的方式会相对简单很多，有兴趣的可以试一试，这里就不再展开介绍了。