【算法】将单链表按值划分

问：

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

答：

笔试：初始化一个Node类型的数组，对数组进行partition，然后把数组中的节点元素串成链表

public static 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];
}

public static 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);
    }
  }
}

面试：定义6个变量，小于部分的头SH=null，小于部分的尾ST=null，等于部分的头EH=null，等于部分的尾ET=null，大于部分的头BH=null，大于部分的尾BT=null

假定按5划分

public static 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;
  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;
  }
  if (eT != null) {
    eT.next = mH;
  }
  return sH != null ? sH : (eH != null ? eH : mH);
}