向单链表添加元素

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
}