如何在java中使用给定的数据向列表中插入节点并维护要排序的列表

Question

如何在保持链表排序的同时向链表中添加100？我知道我必须在单链表的前面添加一项，并使它指向列表的第一个节点，但我很难找到开始这个问题的方法。

       IntegerNode n3 = new IntegerNode(9, null);
       IntegerNode n2 = new IntegerNode(5, n3);
       IntegerNode head = new IntegerNode(1, n2);

       IntegerNode curr;
       IntegerNode prev;

       //print all the items in the linked-list
       for(curr = head; curr!=null; curr = curr.getNext()) {
           System.out.println(curr.getItem());
       }

       int data = 100;

       //insert an node to the list with the given data, and maintain the list to be sorted
    }
}

Answer 1

下面的insert方法应该是一个开始：

public void insert(int val){
    if(this.head==null){ //empty
        this.head = new IntegerNode (val);
        this.head.setNext(null);
        return;
    }
    IntegerNode  prev = null;
    IntegerNode  curr = this.head;
    IntegerNode  newNode = new SLLNode(val);
    while(curr!=null && curr.getVal()<val){
        prev = curr;
        curr = curr.getNext();
    }
    if(prev==null){//new element to be placed at first
        newNode.setNext(curr);
        this.head = newNode;
    }
    else if(curr==null){// new element to be placed at end
        newNode.setNext(null);
        prev.setNext(newNode);
    }else{ //intermediate position
        newNode.setNext(curr);
        prev.setNext(newNode);
    }
}

具体步骤如下：

1. 如果标头为null，则使用当前值创建一个节点并将其设置为根。
2. 否则将遍历列表以查找值小于当前值的最大节点node.We保留对此节点的上一个和下一个节点的引用。
3. 如果prev为null，则表示我们插入的值小于列表中当前的所有值，应放在第一位。
4. 如果d11为null，这意味着我们已经到达列表迭代的末尾，并且我们的值大于list.So中当前的所有节点，我们最终设置了该节点。

希望这能有所帮助。