将字符节点按字母顺序放在链表中

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

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

如果列表为空，则新字符成为列表的头部和尾部。
如果新字符在链表头部节点之前，则它成为链表头部并指向旧链表头部。
如果新字符出现在链表尾部的节点之后，那么它就成为链表的尾部，旧的尾部节点指向它。
如果其中 none 个为真，则该节点位于列表中间的某个位置。

情况 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;
}

而不是 temp = last，我想你在这里想要 last = temp，因为 temp 应该取代它作为列表中的最后一个节点。这就是为什么在输入 "M" 和 "O" 后键入 "N" 时，"O" 消失的原因。

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

将字符节点按字母顺序放在链表中

Putting Character Nodes in Alphabetical Order within a Linked List

java

linked-list

character

alphabetical