1.     // 使用额外空间：把链表节点放入数组中，做分区操作类似快排划分，然后再串起来。
    2.     public static Node ListPartition1(Node head , int privot){
    3.         Node temp = head;
    4.         int count = 0;
    5.         while(temp != null){
    6.             count++;
    7.             temp = temp.next;
    8.         }
    10.         // 构建与node节点等量数组
    11.         Node [] list =new Node [count];
    13.         temp = head;
    15.          // 将链表数拷入数组
    16.         for (int i = 0; i < list.length; i++) {
    17.             list[i] = temp;
    18.             temp = temp.next;
    19.         }
    21.         // 得到划分完值的
    22.          partition(list,privot);
    24.          int i=0;
    25.          for ( i = 1; i < list.length; i++) {
    26.             list[i-1].next =list[i];
    27.         }
    28.          // 不加上会知一直循环
    29.          System.out.println(i);
    30.          list[i-1].next = null;
    32.       return list[0];
    33.     }
    35.     public static void  partition(Node [] arr , int privot){
    37.         int less = -1;
    38.         int more = arr.length;
    39.         int index = 0;
    41.         while(index < more){
    43.             if(arr[index].value < privot){
    45.                 Swap(arr, ++less ,index++);
    47.             }else if(arr[index].value > privot){
    48.                 Swap(arr, --more, index);
    50.             }else{
    51.                 index++;
    52.             }
    53.         }
    55.     }
    57.     public static void Swap(Node [] arr,int i,int j){
    58.         Node temp = arr[i];
    59.         arr[i] = arr[j];
    60.         arr[j] = temp;
    61.     }
    63.     // 不使用额外空间：使用指针来做
    64.     // 六个变量，小于部分头尾 SH=null;ST=null; 等于部分头尾EH=null;ET=null; 
    65.     // 大于部分头尾BH=null;,BT=null;
    66.     // 最开始找到的对应的节点头尾都指向，后面再找到的节点改变尾巴并和头串起来。
    67.     // 最后小于区域的尾巴连等于区域的头，等于区域的尾巴连大于区域的头。    
    68.     public static Node  Listpartition2(Node head , int privot){
    69.         Node sH = null; // small head
    70.         Node sT = null; // small tail
    71.         Node eH = null; // equal head
    72.         Node eT = null; // equal tail
    73.         Node mH = null; // big head
    74.         Node mT = null; // big tail
    75.         Node next = null; // save next node
    76.         while (head != null) {
    77.             next = head.next;
    78.             head.next = null;
    79.             if (head.value < privot) {
    80.                 if (sH == null) { // 第一次找到比privot小的
    81.                     sH = head;
    82.                     sT = head;
    83.                 } else {
    84.                     sT.next = head; // 不是第一次了，尾巴后驱指向新来的小于pivot节点
    85.                     sT = head; // 尾巴指向新来的
    86.                 }
    87.             } else if (head.value == privot) {
    88.                 if (eH == null) {
    89.                     eH = head;
    90.                     eT = head;
    91.                 } else {
    92.                     eT.next = head;
    93.                     eT = head;
    94.                 }
    95.             } else {
    96.                 if (mH == null) {
    97.                     mH = head;
    98.                     mT = head;
    99.                 } else {
    100.                     mT.next = head;
    101.                     mT = head;
    102.                 }
    103.             }
    104.             head = next;
    105.         }
    106.         // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
    107.         if (sT != null) { // 如果有小于区域
    108.             sT.next = eH;
    109.             eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
    110.         }
    111.         // 下一步，一定是需要用eT 去接 大于区域的头
    112.         // 有等于区域，eT -> 等于区域的尾结点
    113.         // 无等于区域，eT -> 小于区域的尾结点
    114.         // eT 尽量不为空的尾巴节点
    115.         if (eT != null) { // 如果小于区域和等于区域，不是都没有
    116.             eT.next = mH;
    117.         }
    118.         return sH != null ? sH : (eH != null ? eH : mH);// 最后判断返回哪个区域的head
    119.     }