问：

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

答：

笔试：初始化一个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);
}