# 1. 题目描述
给定一个单链表，做链表中的数据的三类划分，小于`number`放置在链表左边，等于`nubmer`的数放在中间，大于`number`的数放在右边。
## 1.1 分析
### 解法1
这个题在快速排序算法拓展中做过。那么我们可以将链表中的数据装入数组，然后再在数组中做一次三部分的数据划分。代码如下：
~~~
/**
* 划分链表为三个部分，小于、等于和大于
* @param list 链表
* @param number 比较数字
* @return 链表
*/
public Node partitionList(Node list, int number){
if(list == null || list.next == null) return list;
List<Node> datas = new ArrayList<>();
Node ptr = list;
while(ptr != null){
datas.add(ptr);
ptr = ptr.next;
}
Node[] objects = new Node[datas.size()];
for (int i = 0; i < datas.size(); i++) {
objects[i] = datas.get(i);
}
int left = 0, right = objects.length - 1, k = 0;
while(k <= right){
if(objects[k].val < number){
swap(objects, left, k);
if(left == k) k++;
left++;
} else if(objects[k].val > number){
swap(objects, right, k);
right--;
}else{
k++;
}
}
Node dummyNode = new Node(-1);
ptr = dummyNode;
for (Node object : objects) {
ptr.next = object;
ptr = ptr.next;
}
ptr.next = null;
return dummyNode.next;
}
private void swap(Node[] objects, int left, int i) {
Node temp = objects[left];
objects[left] = objects[i];
objects[i] = temp;
}
~~~
测试用例：
~~~
static class Node{
int val;
Node next;
public Node(int val){
this.val = val;
}
public static Node createLinkedList(int[] arr){
if(arr == null || arr.length == 0) return null;
Node dummyNode = new Node(-1);
Node ptr = dummyNode;
for (int val : arr) {
ptr.next = new Node(val);
ptr = ptr.next;
}
ptr.next = null;
return dummyNode.next;
}
public static void printLinkedList(Node head){
Node ptr = head;
while(ptr != null){
System.out.print(ptr.val+"\t");
ptr = ptr.next;
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = new int[]{1, 5, 4, 8, 3, 1, 4};
Node linkedList = Node.createLinkedList(arr);
Node.printLinkedList(linkedList);
Node node = new ListDemo().partitionList(linkedList, 4);
Node.printLinkedList(node);
}
~~~
结果：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-08 171132.png"/>
因为这个部分的逻辑就来源于快排的扩展部分，这里就不再赘述。
### 解法2
当然有更加简单做法，也就是直接整三个链表，然后分别根据值来添加其位置，代码如下：
~~~
public Node partitionList_2(Node list, int number){
if(list == null || list.next == null) return list;
Node leftPartStart = new Node(-1);
leftPartStart.next = null;
Node midPartStart = new Node(-1);
midPartStart.next = null;
Node rightPartStart = new Node(-1);
rightPartStart.next = null;
Node ptr = list;
while(ptr != null){
Node temp = ptr.next;
if(ptr.val < number){
ptr.next = leftPartStart.next;
leftPartStart.next = ptr;
} else if(ptr.val > number){
ptr.next = rightPartStart.next;
rightPartStart.next = ptr;
} else{
ptr.next = midPartStart.next;
midPartStart.next = ptr;
}
ptr = temp;
}
Node temp = leftPartStart.next;
while(temp!= null && temp.next != null){
temp = temp.next;
}
Node midTemp = midPartStart.next;
while(midTemp != null && midTemp.next != null){
midTemp = midTemp.next;
}
if(temp != null){
temp.next = midPartStart.next;
}
if(midTemp != null){
midTemp.next = rightPartStart.next;
}
return leftPartStart.next;
}
~~~
结果：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-08 194239.png"/>
### 解法3
注意到上面的解法中最终还是需要遍历链表，如果我们可以直接记录左边、中间和右边链表各自的头尾，那么就可以直接链接成链，而不用遍历。解法如下：
~~~
/**
* 更节省空间的做法
* @param list 链表
* @param number 划分数据
* @return 划分后的链表
*/
public Node partitionList_3(Node list, int number) {
if (list == null || list.next == null) return list;
Node leftPartStart = new Node(-1);
Node leftPartEnd = new Node(-1);
leftPartStart.next = leftPartEnd;
leftPartEnd.next = null;
Node midPartStart = new Node(-1);
Node midPartEnd = new Node(-1);
midPartStart.next = midPartEnd;
midPartEnd.next = null;
Node rightPartStart = new Node(-1);
Node rightPartEnd = new Node(-1);
rightPartStart.next = rightPartEnd;
rightPartEnd.next = null;
Node ptr = list, leftP = leftPartStart, midP = midPartStart, rightP = rightPartStart;
while(ptr != null){
Node temp = ptr.next;
if(ptr.val < number){
ptr.next = leftP.next;
leftP.next = ptr;
leftP = leftP.next;
} else if(ptr.val == number){
ptr.next = midP.next;
midP.next = ptr;
midP = midP.next;
}else{
ptr.next = rightP.next;
rightP.next = ptr;
rightP = rightP.next;
}
ptr = temp;
}
if(midPartStart.next != midPartEnd){
leftP.next = midPartStart.next;
}
if(rightPartStart.next != rightPartEnd){
midP.next = rightPartStart.next;
}
rightP.next = null;
return leftPartStart.next;
}
~~~
且因为在这个解法中，一直是按照链接到各自链表尾部的做法，所以对于相同元素而言会按照其出现位置连在对应子链表的后面，所以这个算法是稳定的。
