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

普通方法，将链表节点放到数组然后partition
进阶方法，将链表划分成三个子链表，然后合并

普通方法，将链表节点放到数组然后partition

这个方法比较简单，直接将链表中的值保存到一个数组中，然后按照荷兰国旗的划分方式，将数组划分成左边小于那个数，中间等于那个数，右边大于那个数的形式，(荷兰国旗问题用于快速排序中的partition过程)；
划分完之后，再把数组中的值用链表的形式连接起来。　但是这个方法需要额外的O(n)的空间复杂度，而且partition不能达到稳定性(就是会改变原来的相对顺序)；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 static class Node { public int value; public Node next; public Node(int value) { this.value = value; } } //普通的需要额外空间O(n)且不能达到稳定性的　方法 static Node partitionList_1(Node head, int pivot) { //pivot表示　枢轴；中心点；旋转运动 if (head == null) return null; Node cur = head; int len = 0; while (cur != null) { len++; cur = cur.next; } Node[] nodeArr = new Node[len]; cur = head; for (int i = 0; i < nodeArr.length; i++) { nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr, pivot); for (int i = 1; i < nodeArr.length; i++) { nodeArr[i - 1].next = nodeArr[i]; } nodeArr[nodeArr.length - 1].next = null; //一定要记得把最后一个指针指向null return nodeArr[0]; } //数组划分的paration static void arrPartition(Node[] nodeArr, int pivot) { int less = -1; int more = nodeArr.length; int cur = 0; while (cur < more) { if (nodeArr[cur].value < pivot) { swap(nodeArr, ++less, cur++); } else if (nodeArr[cur].value > pivot) { swap(nodeArr, --more, cur); //注意放到大于区域的时候cur不能++ } else { cur++; } } } //交换两个结点 static void swap(Node[] arrNode, int a, int b) { Node temp = arrNode[a]; arrNode[a] = arrNode[b]; arrNode[b] = temp; }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54`	static class Node { public int value; public Node next; public Node(int value) { this.value = value; } } //普通的需要额外空间O(n)且不能达到稳定性的　方法 static Node partitionList_1(Node head, int pivot) { //pivot表示　枢轴；中心点；旋转运动 if (head == null) return null; Node cur = head; int len = 0; while (cur != null) { len++; cur = cur.next; } Node[] nodeArr = new Node[len]; cur = head; for (int i = 0; i < nodeArr.length; i++) { nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr, pivot); for (int i = 1; i < nodeArr.length; i++) { nodeArr[i - 1].next = nodeArr[i]; } nodeArr[nodeArr.length - 1].next = null; //一定要记得把最后一个指针指向null return nodeArr[0]; } //数组划分的paration static void arrPartition(Node[] nodeArr, int pivot) { int less = -1; int more = nodeArr.length; int cur = 0; while (cur < more) { if (nodeArr[cur].value < pivot) { swap(nodeArr, ++less, cur++); } else if (nodeArr[cur].value > pivot) { swap(nodeArr, --more, cur); //注意放到大于区域的时候cur不能++ } else { cur++; } } } //交换两个结点 static void swap(Node[] arrNode, int a, int b) { Node temp = arrNode[a]; arrNode[a] = arrNode[b]; arrNode[b] = temp; }

进阶方法，将链表划分成三个子链表，然后合并

这个方法是将原来的链表依次划分成三个链表，三个链表分别为small代表的是左边小于的部分，equal代表的是中间相等的部分，big代表的是右边的大于部分；
这三个链表都有自己的两个指针Head和Tail分别代表各自的头部和尾部，分成三个子链表之后，我们只需要遍历链表，然后和给定的值比较，按照条件，向三个链表中添加值就可以了，最后把三个链表连接起来就可以了；

但是，这个题目要注意一些边界条件。具体看下图:

这里写图片描述

代码如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 //第二种　进阶的方法　不需要额外的空间复杂度，且能达到稳定性 static Node partitionList_2(Node head,int piovt){ if(head == null)return null; Node sH = null,sT = null; //小于部分链表的 head 和tail Node eH = null,eT = null; //等于部分链表的　head 和tail Node bH = null,bT = null; //大于部分链表的　head 和tail Node next = null; //用来保存下一个结点 //划分到　三个不同的链表 while(head != null){ next = head.next; head.next = null; //这个是为了链表拼接后　最后一个就不用再去赋值其next域为null 了 if(head.value < piovt){ //向　small 部分　分布 if(sH == null){ //small部分的第一个结点 sH = head; sT = head; }else { sT.next = head; //把head放到small最后一个 sT = head; //更新small部分的sT } }else if(head.value == piovt){ if(eH == null){ eH = head; eT = head; }else{ eT.next = head; eT = head; } }else { if(bH == null){ bH = head; bT = head; }else { bT.next = head; bT = head; } } head = next; } //将三个链表合并(注意边界的判断) if(null != sT) { //合并small和equal部分 sT.next = eH; eT = eT == null ? sT : eT; } if(null != eT){ eT.next = bH; } return sH != null ? sH : eH != null ? eH : bH; }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53`	//第二种　进阶的方法　不需要额外的空间复杂度，且能达到稳定性 static Node partitionList_2(Node head,int piovt){ if(head == null)return null; Node sH = null,sT = null; //小于部分链表的 head 和tail Node eH = null,eT = null; //等于部分链表的　head 和tail Node bH = null,bT = null; //大于部分链表的　head 和tail Node next = null; //用来保存下一个结点 //划分到　三个不同的链表 while(head != null){ next = head.next; head.next = null; //这个是为了链表拼接后　最后一个就不用再去赋值其next域为null 了 if(head.value < piovt){ //向　small 部分　分布 if(sH == null){ //small部分的第一个结点 sH = head; sT = head; }else { sT.next = head; //把head放到small最后一个 sT = head; //更新small部分的sT } }else if(head.value == piovt){ if(eH == null){ eH = head; eT = head; }else{ eT.next = head; eT = head; } }else { if(bH == null){ bH = head; bT = head; }else { bT.next = head; bT = head; } } head = next; } //将三个链表合并(注意边界的判断) if(null != sT) { //合并small和equal部分 sT.next = eH; eT = eT == null ? sT : eT; } if(null != eT){ eT.next = bH; } return sH != null ? sH : eH != null ? eH : bH; }

最后贴上测试完整代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 /** * 将一个链表划分成　左边小于num,中间等于num,右边大于num * 方法1 : 先将链表存到一个数组中，然后使用　　和　荷兰国旗问题相同的方法进行　划分，然后再重新连成一个链表即可(缺点: 额外的空间复杂度和不能做到稳定性) * 方法2 : 使用有限的变量，small equal big 划分成三个链表，这三个链表都分别有自己的头部和尾部，每次一只需要往对应的链表加上相应的数即可 */ public class SmallerEqualBigger { static class Node{ public int value; public Node next; public Node(int value) { this.value = value; } } //普通的需要额外空间O(n)且不能达到稳定性的　方法 static Node partitionList_1(Node head,int pivot){ //pivot表示　枢轴；中心点；旋转运动 if(head == null) return null; Node cur = head; int len = 0; while(cur != null){ len++; cur = cur.next; } Node[] nodeArr = new Node[len]; cur = head; for(int i = 0; i < nodeArr.length; i++){ nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr,pivot); for(int i = 1; i < nodeArr.length; i++){ nodeArr[i-1].next = nodeArr[i]; } nodeArr[nodeArr.length-1].next = null; //一定要记得把最后一个指针指向null return nodeArr[0]; } //数组划分的paration static void arrPartition(Node[] nodeArr, int pivot) { int less = -1; int more = nodeArr.length; int cur = 0; while(cur < more){ if(nodeArr[cur].value < pivot){ swap(nodeArr,++less,cur++); }else if(nodeArr[cur].value > pivot){ swap(nodeArr,--more,cur); //注意放到大于区域的时候cur不能++ }else { cur++; } } } //交换两个结点 static void swap(Node[] arrNode,int a,int b){ Node temp = arrNode[a]; arrNode[a] = arrNode[b]; arrNode[b] = temp; } //第二种　进阶的方法　不需要额外的空间复杂度，且能达到稳定性 static Node partitionList_2(Node head,int piovt){ if(head == null)return null; Node sH = null,sT = null; //小于部分链表的 head 和tail Node eH = null,eT = null; //等于部分链表的　head 和tail Node bH = null,bT = null; //大于部分链表的　head 和tail Node next = null; //用来保存下一个结点 //划分到　三个不同的链表 while(head != null){ next = head.next; head.next = null; //这个是为了链表拼接后　最后一个就不用再去赋值其next域为null 了 if(head.value < piovt){ //向　small 部分　分布 if(sH == null){ //small部分的第一个结点 sH = head; sT = head; }else { sT.next = head; //把head放到small最后一个 sT = head; //更新small部分的sT } }else if(head.value == piovt){ if(eH == null){ eH = head; eT = head; }else{ eT.next = head; eT = head; } }else { if(bH == null){ bH = head; bT = head; }else { bT.next = head; bT = head; } } head = next; } //将三个链表合并(注意边界的判断) if(null != sT) { //合并small和equal部分 sT.next = eH; eT = eT == null ? sT : eT; } if(null != eT){ eT.next = bH; } return sH != null ? sH : eH != null ? eH : bH; } static void printList(Node node){ while(node != null){ System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { System.out.println("----------测试第一种方法----------"); Node head = new Node(9); head.next = new Node(0); head.next.next = new Node(4); head.next.next.next = new Node(5); head.next.next.next.next = new Node(1); printList(head); head = partitionList_1(head,3); printList(head); System.out.println("----------测试第二种方法----------"); Node head2 = new Node(9); head2.next = new Node(0); head2.next.next = new Node(4); head2.next.next.next = new Node(5); head2.next.next.next.next = new Node(1); printList(head2); head2 = partitionList_2(head2,3); printList(head2); } }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149`	/** * 将一个链表划分成　左边小于num,中间等于num,右边大于num * 方法1 : 先将链表存到一个数组中，然后使用　　和　荷兰国旗问题相同的方法进行　划分，然后再重新连成一个链表即可(缺点: 额外的空间复杂度和不能做到稳定性) * 方法2 : 使用有限的变量，small equal big 划分成三个链表，这三个链表都分别有自己的头部和尾部，每次一只需要往对应的链表加上相应的数即可 */ public class SmallerEqualBigger { static class Node{ public int value; public Node next; public Node(int value) { this.value = value; } } //普通的需要额外空间O(n)且不能达到稳定性的　方法 static Node partitionList_1(Node head,int pivot){ //pivot表示　枢轴；中心点；旋转运动 if(head == null) return null; Node cur = head; int len = 0; while(cur != null){ len++; cur = cur.next; } Node[] nodeArr = new Node[len]; cur = head; for(int i = 0; i < nodeArr.length; i++){ nodeArr[i] = cur; cur = cur.next; } arrPartition(nodeArr,pivot); for(int i = 1; i < nodeArr.length; i++){ nodeArr[i-1].next = nodeArr[i]; } nodeArr[nodeArr.length-1].next = null; //一定要记得把最后一个指针指向null return nodeArr[0]; } //数组划分的paration static void arrPartition(Node[] nodeArr, int pivot) { int less = -1; int more = nodeArr.length; int cur = 0; while(cur < more){ if(nodeArr[cur].value < pivot){ swap(nodeArr,++less,cur++); }else if(nodeArr[cur].value > pivot){ swap(nodeArr,--more,cur); //注意放到大于区域的时候cur不能++ }else { cur++; } } } //交换两个结点 static void swap(Node[] arrNode,int a,int b){ Node temp = arrNode[a]; arrNode[a] = arrNode[b]; arrNode[b] = temp; } //第二种　进阶的方法　不需要额外的空间复杂度，且能达到稳定性 static Node partitionList_2(Node head,int piovt){ if(head == null)return null; Node sH = null,sT = null; //小于部分链表的 head 和tail Node eH = null,eT = null; //等于部分链表的　head 和tail Node bH = null,bT = null; //大于部分链表的　head 和tail Node next = null; //用来保存下一个结点 //划分到　三个不同的链表 while(head != null){ next = head.next; head.next = null; //这个是为了链表拼接后　最后一个就不用再去赋值其next域为null 了 if(head.value < piovt){ //向　small 部分　分布 if(sH == null){ //small部分的第一个结点 sH = head; sT = head; }else { sT.next = head; //把head放到small最后一个 sT = head; //更新small部分的sT } }else if(head.value == piovt){ if(eH == null){ eH = head; eT = head; }else{ eT.next = head; eT = head; } }else { if(bH == null){ bH = head; bT = head; }else { bT.next = head; bT = head; } } head = next; } //将三个链表合并(注意边界的判断) if(null != sT) { //合并small和equal部分 sT.next = eH; eT = eT == null ? sT : eT; } if(null != eT){ eT.next = bH; } return sH != null ? sH : eH != null ? eH : bH; } static void printList(Node node){ while(node != null){ System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { System.out.println("----------测试第一种方法----------"); Node head = new Node(9); head.next = new Node(0); head.next.next = new Node(4); head.next.next.next = new Node(5); head.next.next.next.next = new Node(1); printList(head); head = partitionList_1(head,3); printList(head); System.out.println("----------测试第二种方法----------"); Node head2 = new Node(9); head2.next = new Node(0); head2.next.next = new Node(4); head2.next.next.next = new Node(5); head2.next.next.next.next = new Node(1); printList(head2); head2 = partitionList_2(head2,3); printList(head2); } }

测试结果

这里写图片描述