java - 在已排序的 LinkedList 中添加元素

Question

我有一个 ListElement 对象的 LinkedList，我想创建一个递归方法来添加新节点，同时仍然保留列表的排序顺序。

现在我有:

public static ListElement InsertList(ListElement head, ListElement newelem) {

    if (head == null) {
        head = newelem;
        head.next = null;
    } 
    else if (head.next == null) {
        newelem.next = null;
        head.next = newelem;
    }
    else if (head.value < newelem.value) {
        newelem.next = head;
        head = newelem;
    }
    else if (head.value >= newelem.value) {
        head = head.next;
        return InsertList(head, newelem);
    }
    return head;
}

我用代码多次调用它:

ListElement head = null;
ListElement elem;

// this block of code is repeated multiple times with values of 3, 8, 20, and 15
elem - new ListElement();
elem.value = 6;
head = InsertList( head, elem );

输出如下:

6
6 3
8 6 3
20 8 6 3
15 8 6 3

这个输出对于前三行来说是正确的，但之后一切就变得奇怪了。有人可以改进我的算法吗？我觉得 InsertList 方法还可以缩短很多。谢谢!

Answer 1

第四个条件 block 中的 head = head.next 语句正在破坏 head 元素。我相信这应该是

else if(head.value >= newelem.value) {
    head.next = InsertList(head.next, newelem);
}