如何将节点插入到具有给定数据的列表中，并在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. 如果head为null，则用当前值创建一个节点，并将其设置为root。
2. Else遍历列表，找到值小于当前节点的最大节点。我们保留对该节点的上一个和下一个节点的引用。
3. 如果prev是空的，这意味着我们插入的值小于当前列表中的所有值，应该放在第一位。
4. 如果curr是空的，这意味着我们已经到达列表迭代的结束，我们的值大于当前列表中的所有节点。所以我们最后设置了节点。