将单向链表按某值划分为左边小 、链表中间相等 、面试右边大的题根形式
1）将链表放入数组里，在数组上做partition（类似快排），这是笔试时推荐的写法
2）分为小 、中 、小划大三部分，再把各个部分之间串起来，这个是分区面试推荐使用的 。
我们这里重点介绍第二种方法
sH:小于value部分的链表头
sT:小于value部分的尾
eH:等于value部分的头
eT: 等于value部分的尾
bH:大于value部分的头
bT:大于value部分的尾，这个如果不需要保证稳定性的时候可以不要 。
代码实现：
package dataStructure.linkedList.practice;import dataStructure.linkedList.Node;public class SplitByValue {/*** 根据value把原来的面试链表改变为左边小于value 、中间相等value 、题根右边大于value的小划形式* @param head 原链表的头节点* @param value 设定的划分值* @return 返回新链表的头结点*/public static Node<Integer> split(Node<Integer> head, int value) {/*** sH:小于value部分的头 ** sT:小于value部分的尾** eH:等于value部分的头** eT: 等于value部分的尾 ** bH:大于value部分的头** bT:大于value部分的尾，这个如果不需要保证稳定性的时候可以不要 。*/Node sH = null;Node sT = null;Node eH = null;Node eT = null;Node bH = null;Node bT = null;while(head != null) {Node next = head.next;if(head.value < value) {if(sT == null) {sH = head;sT = head;} else {sT.next = head;sT = head;}} else if(head.value == value) {if(eT == null) {eH = head;eT = head;} else {eT.next = head;eT = head;}} else {if(bT == null) {bH = head;bT = head;} else {bT.next = head;bT = next;}}head.next = null;head = next;}//每个元素都划分完毕区间之后，现在开始连接各个区间//如果sT不为null，说明小于区间有值if(sT != null) {sT.next = eH;//不管什么时候都用eT来连接bH,分区但是等于区间可能没有值，// 这个时候我们把小于区间的尾赋值给等于区间的尾eT = eT == null? sT : eT;}//eT不为null有两种情况：1.等于区间有值，eT就是等于区间的尾 2.等于区间无值，eT就是小于区间的尾//两种情况我们都使用eT.next = bH来连接大于区间,这里无需考虑bH是否为空if(eT != null) {eT.next = bH;}//如果小于区间的头不为空，返回小于区间的头//如果小于区间头为空且等于区间的头不为空，返回等于区间的头//其他情况返回大于区间的头return sH != null? sH : eH != null? eH: bH;}public static void main(String[] args) {Node n1 = new Node(3);Node n2 = new Node(5);Node n3 = new Node(2);Node n4 = new Node(4);Node n5 = new Node(3);Node n6 = new Node(3);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n6;Node newHead = split(n1,3);while(newHead != null) {if(newHead.next != null) {System.out.print(newHead.value + "->");} else {System.out.print(newHead.value);}newHead = newHead.next;}}}运行结果：
2->3->3->3->5->4 Process finished with exit code 0
欢迎批评指正
