java - 按升序打印自定义链表的元素

Question

我是 Java 的新手，在开始处理更大的数据结构之前，我会尝试利用空闲时间学习。今晚是关于链接列表的全部内容。我有一个 LinkedList 并试图将列表按升序排列。假设我们有数字 5、4、6、9、1。

您将如何编写方法 - 使其实际变为 1、4、5、6、9？

现在，我正在尝试这样做，而我所拥有的是:

public void order (LinkedList head) {
    if (head == null)
      return;
    else {
      order(head.next);
      System.out.print(" " + head.data);
      return;

它不是按升序打印原始链表的反向:1、9、6、4、5。

我在这里做错了什么？

Answer 1

如果LinkedList是自己定义的类，要么是你

1)自己写sort方法进行排序或者

2) 让您的 Node 类构成您的 LinkedList 以实现 Comparable。创建一个 ArrayList 并将节点添加到其中。之后，您将能够使用 Collections.sort(yourNewArrayList) 对其进行排序。

你会得到类似的东西:

public class Node implements Comparable<Node>{
    private int value;
    //constructor, getters and other members not shown

    @Override
    public int compareTo(Node n){
        return this.getValue() - n.getValue();
    }
}

ArrayList list<Node> = new ArrayList<Node>();
while(linkedList.hasNext()){
    list.add(linkedList.next());
}

Collections.sort(list);

还值得注意的是，Java 实现的排序使用双枢轴快速排序，性能为 O(n(log n)。