在鏈接列表上需要幫助sortedInsert

這個問題想讓我爲我的LList類編寫一個方法，它會將一個新節點添加到正確的位置，假定列表已經按排序順序。我正在處理的列表是一個隊列。在鏈接列表上需要幫助sortedInsert

這裏是我的葉子節點類：

class LNode{ 
    private int val; 
    private LNode next; 
    private LNode prev; 
    public LNode(int v, LNode n, LNode p){ 
     next = n; 
     prev = p; 
     val = v; 
    } 
    public int getVal(){ 
     return val; 
    } 
    public LNode getNext(){ 
     return next; 
    } 
    public LNode getPrev(){ 
     return prev; 
    } 
    public void setVal(int v){ 
     val = v; 
    } 
    public void setNext(LNode n){ 
     next = n; 
    } 
    public void setPrev(LNode p){ 
     prev = p; 
    } 
}

這裏是我的Ltest來類：

public class LTest{ 
    public static void main(String[]args){ 
     LList nums = new LList(); 
     nums.enqueue(55); 
     nums.enqueue(20); 
     nums.enqueue(13); 
     nums.enqueue(11); 
     nums.sortedInsert(15); 


     nums.display(); 
    } 
}

這是我在LLIST類已經試過：

public void sortedInsert(int v){ 
    LNode tmp = head; 
    while(v<tmp.getVal()){ 
     tmp = tmp.getNext(); 
    } 
    tmp.setNext(tmp.getPrev().getNext());//tmp's next is now the original LNode 
    tmp.getPrev().getNext().setPrev(tmp);//the original LNode's previous is now tmp 
    tmp.getPrev().setNext(tmp);//tmp's previous LNode's next is now tmp 
    tmp.setVal(v); 
}

它不工作，輸出是55,20，然後15永遠和Java崩潰。我猜這是因爲tmp LNode指向自己，但對我來說我的代碼並沒有這樣做。那麼誰能告訴我什麼是錯的？謝謝。

來源

2013-03-07 cook cook

從我第一次看你的代碼看起來好像你並沒有實際爲sortedInsert方法中的新值v創建一個新節點。我認爲您需要創建一個新節點，然後通過LinkedList進行迭代，然後附加新節點，而不用擔心設置數據的值，因爲它會在新節點中捕獲。大概是這樣，也許那種...

LNode newnode = new LNode(); 
newnode.setVal(v); 

LNode tmp = head; 

while(v < head.getVal()) 
{ 
    //etc... 
}

不要忘記，如果新節點是在一開始，你需要改變你的頭變量指向newnode。

來源

2013-03-07 02:58:01 Matthew

那麼tmp.getPrev（）。getNext（）不會給我原來的LNode，其中tmp被設置爲等於？ – 2013-03-07 03:06:02

忘了打電話給你...... @Matthew – 2013-03-07 03:06:44

從我的理解，我會說不。當你第一次創建'newnode'時，它根本不會附加到LinkedList上，只是單獨坐在內存中。一旦找到應該插入新節點'newnode'的位置，您就可以正確重新排列所有指針。一些沿着newnode.setPrev（tmp）的行; newnode.setNext（tmp.getNext（））; tmp.setNext（newnode）; newnode.getNext（）setPrev（newnode）。 – Matthew 2013-03-07 03:35:34

在鏈接列表上需要幫助sortedInsert

回答

相關問題