为什么我不能使用此 java 代码对用户定义的 LinkedList 进行排序？

Question

我在 JAVA 中创建了一个程序，用于将元素添加到 LinkedList 并在添加元素时对元素进行排序。我在排序时使用的 swap 技术类似于将节点添加到 LinkedList 的 beginning 时使用的技术。该技术适用于后一种情况，但无法 运行 用于前者。我不明白为什么这不起作用。以下是我的代码供您参考。

//Node class
class Node{
    int d; Node link;
    Node(int d){
        this.d = d;
        link = null;
    }
}//Node

//LinkedList class
class LL{
    Node start;
    LL(){
        start = null; 
    }

    //method to add and sort the nodes 
    //in ascending order of the values of 'd' of the nodes
    void insert(Node nd){
        if(start==null){
            start = nd;
        }
        else{
            Node temp = start;
            while(temp!=null){
                if(nd.d<=temp.d){
                    Node t2 = temp;
                    temp = nd;
                    nd.link = t2;
                    break;
                }
                temp = temp.link;
            }
        }
    }//insert

    //method to display nodes of the LinkedList
    void display(){
        Node temp = start;
        do{
            System.out.print(temp.d + " ");
            temp = temp.link;
        }while(temp!=null);
    }//display
}//LL

//Main class
class LL_Test{
    public static void main(String[] args){
        LL myLL = new LL();
        myLL.insert(new Node(5));
        myLL.insert(new Node(2));
        myLL.insert(new Node(7));
        myLL.insert(new Node(6));
        myLL.insert(new Node(1));
        myLL.display();
    }//main
}//LL_Test

预期输出：1 2 5 6 7
获得的输出：5

Answer 1

两个注释，都适用于 insert()、start != null，在 while(temp!=null) 循环内：

1. 条件不太正确（我认为）-对于升序，您想向前跳转，直到找到具有 temp.d <= nd.d 和 的节点 temp.link==null 或 temp.link.d >= nd.d.
2. 在 insert 中 while 循环的主体中，您设置 nd.link 以便新节点指向另一个节点。但是，您没有设置 temp.link=nd 或任何类似的东西来将新节点挂接到从 start.
开始的链中

Answer 2

除了第一个元素之外，您实际上从未将元素添加到列表中。 （temp = nd;并没有将前一个节点的link设置为nd）。您需要跟踪前一个节点并在第一个大于您想要的节点之前的元素之后添加新节点

void insert(Node nd) {
    Node temp = start;
    Node previous = null;

    while (temp != null && temp.d < nd.d) {
        previous = temp;
        temp = temp.link;
    }

    // insert node
    if (previous == null) {
        // insert at start
        nd.link = start;
        start = nd;
    } else {
        // insert somewhere in the middle
        nd.link = temp;
        previous.link = nd;
    }
}//insert

Answer 3

我对此的看法：

void insert ( Node nd )
{
    Node temp = start;
    Node previous = null;
    while ( temp != null )
    {
        if ( nd.d <= temp.d )
        {
            nd.link = temp;
            if ( nd.d < start.d )
            {
                start = nd;
            }
            break;

        }
        previous = temp;
        temp = temp.link;
    }
    if( previous != null )
    {
        previous.link = nd;
    }
    if( start == null )
    {
        start = nd;
    }


}