java - 将元素添加到单链表

Question

我正在为一个单链整数列表编写一个方法，该方法将在输入它们时对它们进行排序。有些事情不正确，因为我的列表都是空的，或者它们中有随机条目。

public void add(int newEntry){
    Node ptr = start;
    Node insert = null;

    Node newNode = new Node(newEntry, null);

    if (start == null)
        start = newNode;

    while (ptr != null && newEntry >= ptr.data){
        ptr = ptr.next;
    }

    if (ptr == start)
        start = newNode;
    else 
        insert = newNode;
}

Answer 1

if (start == null)
    start = newNode;

您可能想要return在此之后，因为您已完成添加newNode.

if (ptr == start)
    start = newNode;

这将导致旧值的start丢失。大概你想连接newNode到start.

else 
    insert = newNode;

这没有任何作用，因为insert没有在其他任何地方使用。

Answer 2

您没有考虑所有必需的边缘情况。要使此方法起作用，请尝试以下操作：

public void add(int newEntry){

    Node newNode = new Node(newEntry, null);

    if (start == null) {
        start = newNode;
    }

    else if (newEntry <= start.data) {
        newNode.next = start;
        start = newNode;
    }

    else {
        Node ptr = start;
        Node prv = null; // save a reference to previous node
        while (ptr != null && newEntry > ptr.data) {
            prv = ptr;
            ptr = ptr.next;
        }
        prv.next = newNode;
        newNode.next = ptr;
    }

}

Answer 3

我试图尽可能少地改变：

public void add(int newEntry){
    Node ptr = start;
    Node insert = null;

    // the former if is not necessary, will be handled by if at the end

    while (ptr != null && newEntry >= ptr.data){
        insert = ptr; // the node which will point to the new entry
        ptr = ptr.next;
    }

    Node newNode = new Node(newEntry, ptr); // don't forget the rest of the list!

    if (insert == null)
        start = newNode; // first node of empty list or ordered first
    else
        insert.next = newNode; // insertion point found to insert node after
}