我一直在努力工作數小時,試圖按字母順序排列鏈接列表(類似字典)。給定的字符串只是小寫。 例如,輸入:「你好,我的名字是偉業」將在列表中進行排序:節點1:阿爾伯特, 節點2:你好, 節點3:是, 等。按字母順序排列java鏈接列表(類似字典)
我的代碼遠遠讀取像上面的例子一樣的字符串,並將其作爲節點插入 - 無序。
我在網上搜索的方式來排序鏈接列表的字母順序與良好的性能,我發現合併排序可以是有用的。 我已經改變了合併排序爲使用的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());
}
}
你確定你不想使用Java提供的實用程序嗎? 「沒有Collection.sort」的 – SMA
。爲什麼? – Manu
雙旋轉快速排序的平均排序時間非常快。 –