【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个 整 数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5- >1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总 之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部 分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做 要求。 进阶： 在原问题的要求之上再增加如下两个要求。 在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的 顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。 调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到 右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再 讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4， 最后出现5。 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
1 package my_basic.class_3; 2 3 public class Code_12_SmallerEqualBigger { 4 public static class Node{ 5 int value; 6 Node next; 7 public Node(int value) { 8 super(); 9 this.value = value; 10 } 11 } 12 //1. 如果考虑用荷兰国旗，它的辅助空间是数组,三向快排 13 public static Node listPartition1(Node head,int num) { 14 if (head == null) { 15 return head; 16 } 17 Node cur = head; 18 int i=0; 19 while(cur != null) { 20 i++; 21 cur = cur.next; 22 } 23 int[] arr = new int[i]; 24 cur = head; 25 i = 0; 26 while (cur != null) { 27 arr[i++] = cur.value; 28 cur = cur.next; 29 } 30 //调整在数组中的顺序 31 partition(arr,0,arr.length-1,num); 32 cur = head; 33 for (int j = 0; j < arr.length; j++) { 34 cur.value = arr[j]; 35 cur = cur.next; 36 } 37 return head; 38 } 39 public static void partition(int[] arr,int l, int r, int num) { 40 int less= l-1; 41 int more = r+1; 42 while (l < more) { 43 if (arr[l] < num) { 44 swap(arr, l++, ++less); 45 }else if (arr[l] > num) { 46 swap(arr, l, --more); 47 }else { 48 l++; 49 } 50 } 51 } 52 private static void swap(int[] arr, int i, int j) { 53 int tmp; 54 tmp = arr[i]; 55 arr[i]=arr[j]; 56 arr[j]=tmp; 57 } 58 59 //2. 分成 > = < 三个链表 ，再串起来 60 public static Node listPartition2(Node head,int num) { 61 Node lessH = null; 62 Node lessT = null; 63 Node moreH = null; 64 Node moreT = null; 65 Node equalH = null; 66 Node equalT = null; 67 Node next = null; 68 while(head != null) { 69 next = head.next; 70 head.next = null; 71 if (head.value < num) { 72 if (lessH == null) { 73 lessH = head; 74 lessT = head; 75 }else { 76 lessT.next = head; 77 lessT = head; 78 } 79 } 80 if (head.value == num) { 81 if (equalH == null) { 82 equalH = head; 83 equalT = head; 84 }else { 85 equalT.next = head; 86 equalT = head; 87 } 88 } 89 if (head.value > num) { 90 if (moreH == null) { 91 moreH = head; 92 moreT = head; 93 }else { 94 moreT.next = head; 95 moreT = head; 96 } 97 } 98 head = next; 99 } 100 // merge three part 101 if (lessT != null) { 102 lessT.next = equalH; 103 equalT = equalT == null ? lessT : equalT; 104 } 105 if (equalT != null) { 106 equalT.next = moreH; 107 } 108 if (lessH != null) { 109 return lessH; 110 } 111 if (equalH != null) { 112 return equalH; 113 } 114 if (moreH != null) { 115 return moreH; 116 } 117 return null; 118 } 119 120 121 public static void printRandLinkedList(Node head) { 122 Node cur = head; 123 System.out.print("order: "); 124 while (cur != null) { 125 System.out.print(cur.value + " "); 126 cur = cur.next; 127 } 128 System.out.println(); 129 // cur = head; 130 // System.out.print("rand: "); 131 // while (cur != null) { 132 // System.out.print(cur.rand == null ? "- " : cur.rand.value + " "); 133 // cur = cur.next; 134 // } 135 // System.out.println(); 136 } 137 138 public static void main(String[] args) { 139 Node head = new Node(9); 140 head.next = new Node(0); 141 head.next.next = new Node(4); 142 head.next.next.next = new Node(5); 143 head.next.next.next.next = new Node(1); 144 printRandLinkedList(head); 145 // System.out.println("=============="); 146 // copyListWithRand1(head,3); 147 // printRandLinkedList(head); 148 System.out.println("==============="); 149 head =listPartition2(head, 3); 150 printRandLinkedList(head); 151 } 152 153 }