【题目】
给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。
实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
笔试：构建一个Node型数组，将单链表中的节点添加进数组中，在数组中进行操作，再把数组中的每一个Node窜起来
面试：用6个变量来实现，没有用额外的空间
package Algorithms;
/**
* @author : zhang
* @version : 1.0
* @date : Create in 2021/8/10
* @description :
*/
public class SmallerEqualBigger {
public static void main(String[] args) {
Node head1 = new Node(7);
head1.next = new Node(9);
head1.next.next = new Node(1);
head1.next.next.next = new Node(8);
head1.next.next.next.next = new Node(5);
head1.next.next.next.next.next = new Node(2);
head1.next.next.next.next.next.next = new Node(5);
printLinkedList(head1); //Linked List: 7 9 1 8 5 2 5
// head1 = listPartition1(head1, 5);
head1 = listPartition2(head1, 5);
printLinkedList(head1); //Linked List: 1 2 5 5 7 9 8
}
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
//方式1：笔试
public static Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
//统计链表长度
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
//申请一个Node类型的数组
Node[] nodeArr = new Node[i];
cur = head;
//for循环添加单链表中的Node进数组
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
//将数组中的Node进行首尾串联
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
//数组中进行Partition操作（< = >）
public static void arrPartition(Node[] nodeArr, int pivot) {
int small = -1;
int big = nodeArr.length; //big = 7
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
//方式2：面试
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail
Node next = null; // save next node
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
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;
}
// small and equal reconnect
if (sT != null) { //如果有小于区域
sT.next = eH;
eT = eT == null ? sT : eT; //下一步，谁去连大于区域的头，谁就变成eT
}
// all reconnect
if (eT != null) {
eT.next = bH;
}
return sH != null ? sH : eH != null ? eH : bH;
}
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
}