@
greenlake 一到公司就迫不及待，花了有半小时吧，写出来了。包含一个编码、测试，用了 Idea 做调试，直接白板写估计够呛。
-------------------
```
import java.util.*;
class Solution {
class Node {
Node next;
int val;
Node() {
}
Node(int val) {
this.val = val;
}
@
Override public String toString() {
return val + (next != null ? "->" + next.toString() : "");
}
}
boolean check(Node head) {
Node p = head.next;
while (p.next != null) {
if (p.val > p.next.val) {
return false;
}
p = p.next;
}
return true;
}
Node asNode(int[] array) {
Node head = new Node();
Node p = head;
for (int e : array) {
p.next = new Node(e);
p = p.next;
}
return head;
}
void sort(Node head) {
if (head == null || head.next == null)
return;
Node prev = head;
Node curr = prev.next;
while (prev.next != null) {
Node p = head;
boolean changed = false;
while (p != curr) {
if (p == head && curr.val < p.next.val || curr.val >= p.val && curr.val < p.next.val) {
prev.next = curr.next;
Node tmp = p.next;
p.next = curr;
curr.next = tmp;
changed = true;
break;
}
p = p.next;
}
if (changed) {
curr = prev.next;
} else {
prev = prev.next;
curr = prev.next;
}
}
}
}
测试：
Solution solution = new Solution();
{
Solution.Node head = solution.asNode(new int[]{5, 1, 5, 3, 4, 2});
solution.sort(head);
assert solution.check(head);
}
{
Solution.Node head = solution.asNode(new int[]{1});
solution.sort(head);
assert solution.check(head);
}
for (int times = 0; times < 1000; times++) {
int len = 2000;
int[] test = new int[len];
Random random = new Random();
for (int i = 0; i < len; i++)
test[i] = random.nextInt();
Solution.Node head = solution.asNode(test);
solution.sort(head);
assert solution.check(head);
}
```