在已排序的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

第四个条件块中的head = head.next语句正在破坏head元素。我认为应该改成

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

Answer 2

当您尝试插入15时，您输入了第四个条件:

// 20 > 15
else if (head.value >= newelem.value)

依次调用InsertList，但传递8作为头节点，从而进入第三个条件:

// 8 < 15
else if (head.value < newelem.value) 

这里是

newelem.next = head;

设置15 -> next = 8

然后你说

head = newelem;

设置head = 15

你看到问题了吗?使用@Zim-Zam O'Pootertoot的答案来修复你的错误

Answer 3

感谢大家的帮助和回答!
我找到了另一个类似的帖子，其中一个答案似乎对我有用。这里有一个链接，任何人想看看:https://stackoverflow.com/a/15936744/1470257