Write code to partition a linked list around a value x, such that all nodes less than x
come before alt nodes greater than or equal to.
分割一个链表，将值小于x的节点全部放在其他节点的前面。
解答：
我们可以创建两个不同的链表，其中一个用来连接比x小的节点，另外一个则连接大于等于x的节点，然后合并两个链表即可。
public class Main {
public static void appendToTail(List head, int d) {
List end = new List(d);
List n = head;
while (n.next != null) {
n = n.next;
}
n.next = end;
}
public static void print(List head) {
List n = head;
System.out.print("{");
while (n != null) {
if (n.next != null)
System.out.print(n.data + ", ");
else
System.out.println(n.data + "}");
n = n.next;
}
}
public static List partition(List head, int x) {
List small = null;
List large = null;
List largeHead = null;
List smallHead = null;
while (head != null) {
List next = head.next;
head.next = null;
if (head.data < x) {
if (small == null) {
small = head;
smallHead = small;
} else {
small.next = head;
small = small.next;
}
} else {
if (large == null) {
large = head;
largeHead = large;
} else {
large.next = head;
large = large.next;
}
}
head = next;
}
if(small == null)
{
return largeHead;
}
small.next = largeHead;
return smallHead;
}
public static void main(String args[]) {
List list = new List(0);
appendToTail(list, 9);
appendToTail(list, 8);
appendToTail(list, 7);
appendToTail(list, 6);
appendToTail(list, 5);
appendToTail(list, 4);
appendToTail(list, 3);
appendToTail(list, 2);
appendToTail(list, 1);
print(list);
print(partition(list, 5));
}
}
class List {
int data;
List next;
public List(int d) {
this.data = d;
this.next = null;
}
public List() {
}
}