實現反向排序LinkedList

我想實現一個鏈接列表，在Java中以相反的順序排序，但add方法給了我奇怪的結果。我必須實現這個列表（不能只使用LinkedList，這是我在實踐中會做的），我必須使用遞歸。實現反向排序LinkedList

我將測試代碼的數組：

[-20, 0, -10, 5, 12, 1, -100, -50, -101, 200]

繼承人是從SortedLinkedSet的相關位：

public boolean add(T el) { 
if (firstNode == null || el.compareTo(firstNode.getValue()) > 0) { 
    //the new element will become the new first node 
    firstNode = new SortedLinkedSetNode<T>(el, firstNode); 
    return true; 
} else { 
    return firstNode.add(el); 
} 
}

這裏的SortedLinkedSetNode：

public boolean add(T el) { 


    //reduction steps 
     if(el == null) 
      return false; 
     else if(contains(el)) 
      return false; 
     else if(el.compareTo(this.getValue()) <= 0) 
     { 
      if(next == null) 
      { 
       next = new SortedLinkedSetNode<T>(el); 
       return true; 
      } 

      return next.add(el); 
     } 
     else 
     { 
      //base case 
      SortedLinkedSetNode<T> newNode = new SortedLinkedSetNode<T>(el); 
      newNode.next = this.next; 
      this.next = newNode; 
      return true; 
     } 
    }

輸出：

[200, 12, 5, 0, 1, -20, -10, -100, -50, -101]

將if(next == null)檢入else if區塊之前else if(el.compareTo(this.getValue()) <= 0)給出了相同的結果。

我已經無法使頭或這些結果的尾巴了幾個小時：\

爲了測試，我剛剛被檢查內存中的列表。在任何人問起之前，這確實是功課。我不是在尋找講義，只是幫助。

來源

2014-03-02 Prime

你重寫了compareTO嗎？ – stinepike

爲什麼不只是實現一個「正常」排序的鏈表，而是使用「反向比較器」來代替？ – fge

@StinePike yes它會返回節點值的compareTo（即Integer.compareTo） – Prime

你的基本情況是不正確的。如果el>this.getValue()您仍然在當前節點之後插入它，這會破壞您的訂單不變量。

您可以做的一件事是在當前後插入新節點，然後將新節點的值更改爲當前節點的值，並將當前節點的值更改爲el。

來源

2014-03-02 09:41:30

感謝您的回覆。您的建議大大提高了排序，但由於某種原因，一個Integer仍然不合適。結果：[200，12，5，1，0，-20，-10，-100，-50，-101]任何想法爲什麼-20和-10切換？ – Prime

新的基本情況是：\t \t'SortedLinkedSetNode newNode = new SortedLinkedSetNode （getValue（））; newNode.next = this.next; this.next = newNode; value = el;' – Prime

您可能需要添加一些臨時調試打印以顯示您的代碼正在執行的操作。你在什麼順序插入元素？ –

實現反向排序LinkedList

回答

相關問題