Нужна помощь по Связанному списку sortedInsert

Question

Вопрос требует, чтобы я написал метод для моего класса LList, он добавит новый узел в правильную позицию, предполагая, что список уже отсортирован. Список, с которым я имею дело, - это очередь.

Вот мой LNode класс:

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 указывает на себя, но для меня мой код этого не делает. Так может кто-нибудь сказать мне, что случилось? Спасибо.

Answer 1

С первого взгляда на ваш код это выглядит так, как будто вы фактически не создаете новый узел для нового значения v в методе sortedInsert. Я думаю, вам нужно будет создать новый узел, а затем выполнить его через LinkedList, а затем присоединить новый узел и не беспокоиться о настройке значения данных, потому что он будет захвачен в новом узле. Вид-то вроде этого, может быть ...

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

LNode tmp = head; 

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

Не забывайте, что если новый узел в начале вам нужно изменить переменную голову, чтобы указать на newnode.