我應該如何實現使用我的自定義鏈表進行排序？

我一直想弄清楚鏈接列表是如何工作的，但我很難想象這個概念。我知道多種算法，但我無法弄清楚如何實現它們。我應該如何實現使用我的自定義鏈表進行排序？

這裏是我的代碼：

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：我也有一個多項式類，它接受一個字符串並將它變成一個LL。我不認爲有必要發佈它，但如果你需要它，我會發布它！謝謝！

來源

2014-11-16 John B

排序鏈表是真的效率低下，通常你會上市的列表複製到一個數組，對它們進行排序和複製他們回來（這是JDK做什麼）

BTW除非你真的有稀疏indecies，你是使用數組或列表最好。這不僅更簡單，更高效和更快速，而且也是自然排序的。

一個數組將使用一部分內存和一個鏈表，即使你有很多零係數。

來源

2014-11-16 11:27:49

我明白了，我會這樣做，但我需要使用鏈接列表 –

@JohnB在這種情況下，請執行JDK的操作，將其複製到數組中，對數組進行排序並將值複製回來。這種排序是O（N log N），而不是O（N^2）的冒泡排序/插入排序， –

我應該如何實現使用我的自定義鏈表進行排序？

回答

相關問題