Java排序一个整数链表

Question

我创建了一个整数链表，但我不知道如何排序!我试了很多次，但总是在名单里的数字消失了这是我用于链表的代码!

import java.util.Random;
class Node {
Node next;
int num;
public Node(int val) {
    num = val;
    next = null;
}
}
public class LinkedList {
Node head;
public LinkedList(int val) {
    head = new Node(val);
}
public void append(int val) {
    Node tmpNode = head;
    while (tmpNode.next != null) {
        tmpNode = tmpNode.next;
    }
    tmpNode.next = new Node(val);
}
public static void main(String[] args) {
    Random rn=new Random();
    int min=0;
    int max=1000;
    LinkedList myList = new LinkedList(rn.nextInt((max - min) + 1) + min);
    for(int i=0;i<100;i++){
        int x=rn.nextInt((max - min) + 1) + min;
        myList.append(x);
    }
    myList.print();
}
}

Answer 1

这一行

LinkedList myList = new LinkedList(rn.nextInt((max - min) + 1) + min);

根据LinkedList API，

似乎没有多大意义。你应该真正使用Java的LinkedLists，而不是你自己的，这样你就可以利用列表和集合api和泛型。

一旦你使用java.util.LinkedList你可能想调用

myList.sort();

对列表进行排序，或者提供一个比较器，如下所示:

  import java.util.Comparator;
  import java.util.LinkedList;
  Comparator<Integer> order = Integer::compare;
  myList.sort(order.reversed());

顺便说一下，蜘蛛鲍里斯的评论是正确的。这就是java 8的标准实现对LinkedLists的做法，它使列表成为一个数组，在O(n log n)中对数组进行排序，然后将每个项放在O(n)中的位置:

 default void sort(Comparator<? super E> c) { //O(n log n)
    Object[] a = this.toArray(); //O(n)
    Arrays.sort(a, (Comparator) c); //O(n log n)
    ListIterator<E> i = this.listIterator();
    for (Object e : a) { //O(n)
        i.next();      //O(1)
        i.set((E) e);  //O(1)
    }
}

顺便说一下:我在你的代码中没有看到任何"print()"方法的实现。确定它打印正确的值吗?我在你的代码中没有看到任何排序方法的实现，所以我们怎么知道排序时数字是怎么丢失的呢?