给定一个链表,再给定一个整数 pivot,请将链表调整为左部分都是值小于 pivot 的节点,中间部分都是值等于 pivot 的节点, 右边部分都是大于 pivot 的节点。
除此之外,对调整后的节点顺序没有更多要求。
import java.util.Scanner;
public class Main {
static class Node {
Node next;
int val;
public Node(int val) {
this.val = val;
}
}
private static Node solve(Node head, int pivot) {
if (head == null || head.next == null) {
return head;
}
Node lessHead = null;
Node lessTail = null;
Node equalHead = null;
Node equalTail = null;
Node moreHead = null;
Node moreTail = null;
Node cur = head, next;
while (cur != null) {
next = cur.next;
cur.next = null;
if (cur.val < pivot) {
if (lessTail == null) {
lessHead = cur;
lessTail = cur;
} else {
lessTail.next = cur;
lessTail = cur;
}
} else if (cur.val == pivot) {
if (equalTail == null) {
equalHead = cur;
equalTail = cur;
} else {
equalTail.next = cur;
equalTail = cur;
}
} else {
if (moreTail == null) {
moreHead = cur;
moreTail = cur;
} else {
moreTail.next = cur;
moreTail = cur;
}
}
cur = next;
}
if (lessTail != null) {
lessTail.next = equalHead;
if (equalTail == null) {
equalTail = lessTail;
}
}
if (equalTail != null) {
equalTail.next = moreHead;
}
return lessHead == null ? (equalHead == null ? moreHead : equalHead) : lessHead;
}
private static void print(Node node) {
StringBuilder res = new StringBuilder();
while (node != null) {
res.append(node.val).append(" ");
node = node.next;
}
System.out.println(res.subSequence(0, res.length() - 1));
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int pivot = in.nextInt();
Node head = new Node(in.nextInt());
Node pre = head;
while (--n > 0) {
Node node = new Node(in.nextInt());
pre.next = node;
pre = node;
}
Node node = solve(head, pivot);
print(node);
}
}
}