将单向链表按某值划分成左边小、中问相等、右边大的形式

类似于荷兰国旗问题 分成小、中、大三部分，再把各个部分之问串起来(注意边界问题)

public Node listPartition2(Node head, int pivot) {
  Node sH = null; // 小头
  Node sT = null; // 小尾
  Node eH = null; // 等头
  Node eT = null; // 等尾
  Node mH = null; // 大头
  Node mT = null; // 大尾
  Node next = null;

  // 1. 划分为三个区域
  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;
  }

  // 2. 小尾连等头，等尾连大头
  if (sT != null) {
    sT.next = eH;
    eT = (eT == null ? sT : eT); // 等头为空 代表等区为空；等头就是小尾
  }

  if (eT != null) {
    eT.next = mH;
  }

  return sH != null ? sH : (eH != null ? eH : mH); // 如果小头为null 返回等头；若等头为null，返回大头
}

把链表放入数组里，在数组上做 partition #

public Node listPartition1(Node head, int pivot) {
  if (head == null)
    return head;
  Node cur = head;
  int i = 0;
  while (cur != null) { // 统计链表节点个数
    i++;
    cur = cur.next;
  }

  // 将链表节点放入数字中 进行区域划分
  Node[] nodeArr = new Node[i];
  i = 0;
  cur = head;
  for (i = 0; i != nodeArr.length; i++) {
    nodeArr[i] = cur;
    cur = cur.next;
  }

  arrPartition(nodeArr, pivot);
  for (i = 1; i != nodeArr.length; i++) {
    nodeArr[i - 1].next = nodeArr[i];
  }
  nodeArr[i - 1].next = null;
  return nodeArr[0];
}

private void arrPartition(Node[] nodeArr, int pivot) {
  int small = -1;
  int big = nodeArr.length;
  int index = 0;
  while (index != big) {
    if (nodeArr[index].value < pivot) {
      swap(nodeArr, ++small, index++);
    } else if (nodeArr[index].value == pivot) {
      index++;
    } else {
      swap(nodeArr, --big, index);// ...
    }
  }
}