# 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;
}
~~~
且因為在這個解法中，一直是按照鏈接到各自鏈表尾部的做法，所以對于相同元素而言會按照其出現位置連在對應子鏈表的后面，所以這個算法是穩定的。
