如何将一个链表按指定数字进行分区？

前言

本文介绍如何将一个链表按指定模式进行分区，例如分为小、中、大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部分，然后再把几个部分给串起来，本次的解题方法需要点编码技巧，除了这种方式外，还可以使用数组分区的方式会相对简单很多，有兴趣的可以试一试，这里就不再展开介绍了。