java - 按字母顺序排序 Java 链表(类似字典)

Question

我已经工作了几个小时，试图按字母顺序(类似于字典)对字符串链接列表进行排序。给定的字符串仅为小写。例如，输入:“你好，我的名字是阿尔伯特”将在列表中排序为:节点 1:阿尔伯特，节点2:你好，节点3:是，等等..

到目前为止，我的代码读取一个类似于上面示例的字符串，并将其作为节点插入 - 无序。

我在网上搜索了按字母顺序对链接列表进行良好性能排序的方法，我发现合并排序非常有用。我已经使用 compareTo() 更改了合并排序以适用于字符串，但我的代码在以下行中返回 nullPointerException 错误:

if(firstList._word.compareTo(secondList._word) < 0){

我正在寻求帮助来修复以下代码或其他按字母顺序对链接列表进行排序的方法(不使用 Collection.sort)

我的完整代码是(在尝试添加合并排序以与我的代码一起使用之后):

public class TextList
{
    public WordNode _head;

    public TextList() 
    {
    _head = null;
    }

    public TextList (String text)
    {
        this._head = new WordNode();
        int lastIndex = 0;
        boolean foundSpace = false;
        String newString;
        WordNode prev,next;
        if (text.length() == 0) {
            this._head._word = null;
            this._head._next = null;
        }
        else {
        for (int i=0;i<text.length();i++)
        {
                if (text.charAt(i) == ' ') {
               newString = text.substring(lastIndex,i);
               insertNode(newString);
               // Update indexes
                lastIndex = i;
                // set to true when the string has a space
                foundSpace = true;  
        }
    }
        if (!foundSpace) {
            //If we didnt find any space, set the given word
            _head.setWord(text);
            _head.setNext(null);

        }
        else {
            //Insert last word
            String lastString = text.substring(lastIndex,text.length());
            WordNode lastNode = new WordNode(_head._word,_head._next);
            _head.setNext(new WordNode(lastString,lastNode));

        }

        sortList(_head);

    }
}

      private void insertNode(String word)
      {
      //Create a new node and put the curret node in it
      WordNode newWord = new WordNode(_head._word,_head.getNext());
      //Set the new information in the head
      _head._word = word;
      _head.setNext(newWord);
    }

private WordNode sortList(WordNode start) {
        if (start == null || start._next == null) return start;
        WordNode fast = start;
        WordNode slow = start;
        // get in middle of the list :
        while (fast._next!= null && fast._next._next !=null){
            slow = slow._next; fast = fast._next._next;
        }
        fast = slow._next;
        slow._next=null;
        return mergeSortedList(sortList(start),sortList(fast));
        }

        private WordNode mergeSortedList(WordNode firstList,WordNode secondList){
            WordNode returnNode = new WordNode("",null);
            WordNode trackingPointer = returnNode;
            while(firstList!=null && secondList!=null){
                if(firstList._word.compareTo(secondList._word) < 0){
                    trackingPointer._next = firstList; firstList=firstList._next;
                }
                else {
                    trackingPointer._next = secondList; secondList=secondList._next
                    ;}
                trackingPointer = trackingPointer._next;
            }
            if (firstList!=null) trackingPointer._next = firstList;
            else if (secondList!=null) trackingPointer._next = secondList;
            return returnNode._next;
            }

        public String toString() {
            String result = "";
            while(_head.getNext() != null){
                _head = _head.getNext();
                result += _head._word + ", ";
            }
            return "List: " + result;
}


    public static void main(String[] args) {
        TextList str = new TextList("a b c d e a b");
        System.out.println(str.toString());
    }

}

Answer 1

过去我制作了一种方法，可以将数组中的字符串按字母顺序排序作为学校硬件，所以嗯，它是:

    private void sortStringsAlphabetically(){
    for (int all = 0; all < names.length; all++) {
        for (int i = all + 1; i < names.length; i++) {
            if (names[all].compareTo(names[i]) > 0) {
                String tmp = names[i];
                names[i] = names[all];
                names[all] = tmp;
            }
        }
    }
}

这段代码适用于数组，特别是名称数组。您可以调整它以使用列表，这非常简单，特别是如果我们考虑 List 接口(interface)中的各种方法及其所有实现。

干杯。