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

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)编写自己的排序方法来执行排序或

2)让构成LinkedList的Node类实现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) )性能。

Answer 2

您有两个选择，具体取决于您的目标：

对于可以正常工作的代码，请使用java.util.LinkedList或java.util.ArrayList和java.util.Collections.sort()。它们是由非常优秀的程序员编写的，并且一直被世界各地数以百万计的程序员使用。

• 如果你对学习数据结构的细节感兴趣，那么你似乎已经编写了你自己的LinkedList类。现在，您需要编写自己的sort()方法。排序是一个非常好理解的问题，有许多在线资源可以解释不同的排序算法。这些都是很好的学习工具，因为有太多不同的优点和缺点的变体。