/**
* 将单向链表按某值划分为左边小，中间相等，右边大的形式
*/
public class NodePartition {
/**
* 将链表分为 小于、等于、大于 的三个链表，然后连成一个链表
*
* @param head 链表
* @param key 指定值
* @return 新链表
*/
public Node partition(Node head, int key) {
if (head == null || head.next == null) {
return head;
}
Node lessLeft = null;
Node lessRight = null;
Node equalLeft = null;
Node equalRight = null;
Node moreLeft = null;
Node moreRight = null;
Node next = null;
while (head != null) {
// 分离剩余节点
next = head.next;
// 分离头节点
head.next = null;
if (head.value < key) {
if (lessLeft == null) {
lessLeft = head;
lessRight = head;
} else {
lessRight.next = head;
lessRight = lessRight.next;
}
} else if (head.value == key) {
if (equalLeft == null) {
equalLeft = head;
equalRight = head;
} else {
equalRight.next = head;
equalRight = equalRight.next;
}
} else {
if (moreLeft == null) {
moreLeft = head;
moreRight = head;
} else {
moreRight.next = head;
moreRight = moreRight.next;
}
}
// 将头节点指向剩余节点
head = next;
}
// 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
if (lessRight != null) {
lessRight.next = equalLeft;
equalRight = equalRight == null ? lessRight : equalRight;
}
if (equalRight != null) {
equalRight.next = moreLeft;
}
return lessLeft != null ? lessLeft : (equalLeft != null ? equalLeft : moreLeft);
}
/**
* 把链表放在数组里，数组做partition，之后再把链表拼回去
*/
// public Node partition(Node head, int key) {}
/**
* 链表结构
*/
public static class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
}
/* 如有意见或建议，欢迎评论区留言；如发现代码有误，欢迎批评指正 */