java - 在链接列表中按字母顺序放置字符节点

Question

我已经尝试弄清楚如何做到这一点有一段时间了，但我就是不知道我做错了什么。我需要做的是使用字符创建一个链接列表，并按字母顺序显示该列表。

主程序:

public static void main(String[] args) {

    String n = null;
    char newChar = ' ';
    KeyboardReader reader = new KeyboardReader();

    Node start = null;
    Node last = null;
    Node temp = null;

            do{
                System.out.print("Enter a letter: ");
                newChar = reader.readChar();

                temp = new Node(newChar);

                if (start == null)
                     start = temp;
                if (last != null){ 
                    last.nodeptr = temp;
                }
                last = temp;

                System.out.print("Linked list: ");
                printList(start);

                System.out.print("Would you like to enter another letter (y/n)? ");
                n = reader.readLine();
                addLine();

            }while(n.compareTo("y") == 0);

            System.out.println("The following will output a linked list created in alphabetical order.");
            addLine();

            start = null;
            last = null;
            temp = null;

            do{
                System.out.print("Enter a letter: ");
                newChar = reader.readChar();

                temp = new Node(newChar);

                if(start == null){
                    start = temp;
                    last = temp;
                }

                //~~ CAUSING ISSUES ~~
                //if(last != null)
                    //last.nodeptr = temp;


                //insert before
                if(temp.letter < start.letter){
                    temp.nodeptr = start;
                    start = temp;   
                }

                //insert at middle or end
                else{
                    if(last.letter < temp.letter){
                        last.nodeptr = temp;
                        temp = last;
                    }
                    if(last.letter > temp.letter){
                        temp.nodeptr = last;
                        last = temp;
                    }
                }

                //For testing purposes
                /*else{
                    if(temp.letter > start.letter){
                        if(start.nodeptr != null){
                            while(temp.letter > start.nodeptr.letter){
                                temp.nodeptr = start;
                                start = temp;
                            }
                        }
                    }
                    else if(temp.letter < last.letter){
                        if(last.nodeptr != null){
                            while(temp.letter < last.nodeptr.letter){
                                last.nodeptr = temp;
                                last = temp;
                            }
                        }
                    }
                }
                */

                System.out.print("Linked list: ");
                printList(start);

                System.out.print("Would you like to enter another letter (y/n)? ");
                n = reader.readLine();
                addLine();

            }while(n.compareTo("y") == 0);
}    

当前输出(与注释掉的内容一样):

Enter a letter: m  
Linked list: m  
Would you like to enter another letter (y/n)? y  

Enter a letter: o  
Linked list: mo  
Would you like to enter another letter (y/n)? y  

Enter a letter: n  
Linked list: mon  
Would you like to enter another letter (y/n)? y  

Enter a letter: e   
Linked list: mone  
Would you like to enter another letter (y/n)? y  

Enter a letter: y  
Linked list: money  
Would you like to enter another letter (y/n)? n  

The following will output a linked list created in alphabetical order.  

Enter a letter: m  
Linked list: m  
Would you like to enter another letter (y/n)? y  

Enter a letter: o  
Linked list: mo  
Would you like to enter another letter (y/n)? y  

Enter a letter: n  
Linked list: mn  
Would you like to enter another letter (y/n)? n     

我弄清楚了程序的第一部分，它只是在用户输入每个字符时插入。但是，现在我必须按字母顺序排列它，我想我已经找到了我的问题，我认为这是由于最后一个节点造成的。我在程序中注释掉它并运行，但不正确。如果我不注释它，它会形成一个循环并基本上破坏程序。

如果有人可以帮助我修复代码并使其 100% 正常工作，我将不胜感激!

Answer 1

当您向列表中添加新角色时，基本上有四种情况需要考虑:

1. 如果列表为空，则新字符将同时成为列表的头部和尾部。
2. 如果新字符位于列表头部的节点之前，则它成为列表的头部并指向列表的旧头部。
3. 如果新字符出现在链表尾部节点之后，则它成为链表尾部，旧尾部节点指向它。
4. 如果这些都不成立，则该节点将位于列表中间的某个位置。

情况 1 和 2 看起来是正确的:

if(start == null){
    start = temp;
    last = temp;
}

//insert before
if(temp.letter < start.letter){
    temp.nodeptr = start;
    start = temp;   
}

案例 3 有一个小错误:

if(last.letter < temp.letter){
    last.nodeptr = temp;
    temp = last;
}

我认为您需要 last = temp 在这里，而不是 temp = last，因为 temp 应该取代它作为最后一个列表中的节点。这就是为什么当您在输入“M”和“O”后输入“N”时，“O”消失了。

案例 4 是您需要做一些工作的案例。因为新节点可以位于列表中的任何位置，并且列表可以包含任意数量的元素，所以您无法像之前那样仅使用一系列 if 语句来完成此操作。到目前为止已完成。相反，您需要使用循环来遍历列表并找到插入新节点的适当位置。这足以让您继续前进吗？