按字母顺序排列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

如果你不'不想有一个庞大的代码谁得到这个词的每个第一个字母和排序他们，用Collection.sort（）做它

我不知道什么是在Collection.sort（）的proplem，所以使用它

下面是一个简短的代码，这并不exactually这就是你想要什么：

String test = "hello my name is albert"; 
test = test.replaceAll(" ", "\n"); 
String[] te = test.split("\n"); 
List<String> stlist = new ArrayList<String>(); 
for(String st : te) { 
    stlist.add(st); 
} 
Collections.sort(stlist); 

Answer 2

在过去我曾到字符串数组作为学校HW按字母顺序排序的方法，所以乌姆这里是：

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界面及其所有实现中的各种方法。

干杯。

Answer 3

关于NPE你说这可能是因为你头上有一个空字符串，并继续添加插入方法。

this._head = new WordNode(); 

此外，添加最后一个元素也不合适。只是重用像下面

insertNode(text.substring(lastIndex,text.length())); 

这是当你将字符串转换到内衬列表

您可以使用下面的代码来处理第一空

private void insertNode(String word) { 
    if (this._head == null) { 
     this._head = new WordNode(word, null); 
    } else { 
     WordNode newWord = new WordNode(_head._word, _head.getNext()); 
     _head._word = word; 
     _head.setNext(newWord); 
    } 
} 

我以为有问题的那些插入方法