java - 我应该如何使用自定义链表实现排序？

Question

我一直在试图弄清楚链接列表是如何工作的，但我很难想象这个概念。我知道多种算法，但我不知道如何实现它们。

这是我的代码:

public class LL {
    private ListNode front,last; 

    public LL(){
        front = null; last = null;
    }

    //
    //methods here...
    //

    public class ListNode{
        public double coefficient;
        public int exponent;
        public ListNode next;

        public ListNode(){
            this(0, 0, null);
        }

        public ListNode(double coefficient, int exponent, ListNode next){
            this.coefficient = coefficient; 
            this.exponent = exponent;
            this.next = next;
        }
    } 
}

用于存储多项式数据。我试图让它们按降序排列。最终将相同指数的节点的系数相加。

我想我会采用冒泡排序算法，但我不知道如何重新排列链接。我还考虑添加一个remove()方法，只删除一个节点并将其添加到最后，直到它被排序。但这非常低效，因为我每次都必须不断创建新节点。

PS:我还有一个 Polynomial 类，它接受一个字符串并将其转换为 LL。我认为没有必要发布它，但如果你需要它，我会发布它! 谢谢!

Answer 1

对链表进行排序确实效率很低，通常你会将列表复制到一个数组中，对它们进行排序，然后将它们复制回来(这就是 JDK 所做的)

顺便说一句，除非你真的有稀疏的不确定性，否则最好使用数组或数组列表。这不仅更简单、更高效、更快，而且是自然排序的。

即使有相当多的零系数，数组也会使用内存和链表的一小部分。