java - Java 中的字符串归并排序 - 链表

Question

我有一个练习，我必须在一个链表中插入一个字符串。假设字符串如下:

"Java Coding Is Great"

合并排序后，链表应该是这样的:

coding >>> great >>> is >>> java.

问题是在我的合并排序代码中我收到以下内容:

 great >> is >> java >> coding 

所有单词都已排序，但第一个单词(原始列表的开头)未排序。

我有两个类:TextList 和 WordNode。

WordNode 类有两个属性:

String _word; WordNode _next; //an address to the next link

TextList类只有一个属性:链表头部地址:

WordNode _head;

我有一个构造函数，我在其中将字符串随机插入到链表中。最后它开始合并排序列表。该算法适用于本练习。

public TextList(String text){
     String s=""; int index=text.length();
    //we will stop at the end of the String.
    for (int i=text.length()-1; i>=0; i--){
        //if we reached a space, insert each string in appropriate order, 
        //the first word is the head of the string and last word points to null.
        if (!(text.charAt(i)>='a' && text.charAt(i)<='z')){ 
            s=text.substring(i,index);
            _head=new WordNode(s,_head);
            s="";
            index=i;
        }
        if (i==1){
            s=text.substring(i-1,index);
            _head=new WordNode(s,_head);
        }
    }

//start merge sotring the list.
    this._head=this._head.mergeSort();
}

合并排序方法:合并排序、合并和拆分:(这些在 WordNode 类中):

归并排序方法

public WordNode mergeSort(){
    return mergeSort(this);
}
private WordNode mergeSort(WordNode h){
    // Sort h by recursively splitting and merging
    if (h==null || h._next==null)
        return h;
    else{
        WordNode evens=h.splitOdds();
        WordNode odds=h.splitEvens();
        return mergeSort(odds).merge(mergeSort(evens)); 
    }
}

合并方法

private WordNode merge(WordNode h){
        //method merges this's list with h's list

        //if h is null, just return this.
        if (h==null){
            return this;
        }
        if (this._word.compareTo(h._word)<0){
            if (this._next==null)
                return new WordNode(this._word,h);
            else
                return new WordNode(this._word,this._next.merge(h));
        }
        else
            return new WordNode (h._word, merge(h._next));

    }

分割方式:一种为偶数位，一种为奇数位。

private WordNode splitOdds(){
    boolean flag=true;
    WordNode odds=null;
    WordNode ptr=this;
    while (ptr!=null){  
        if(flag)
        odds=new WordNode(ptr._word,odds);
        ptr=ptr.getNext();
        flag=!flag;
    }
    return odds;
}
//MUST BE INITILIZED ON HEAD
    private WordNode splitEvens(){
        boolean flag=true;
        WordNode evens=null;
        WordNode ptr=this._next;
        while (ptr!=null){
            if (flag)
                evens=new WordNode(ptr._word,evens);
                ptr=ptr.getNext();
                flag=!flag;
            }



        return evens;
    }

请帮我找出问题所在。 不幸的是，我不能使用第三类，我不能使用指向列表开头或结尾的指针。

Answer 1

您能否使用调试器单步执行代码？这将帮助您查明问题所在。即使是一些明智地放置的断点也会有所帮助。

从仅包含一个条目的列表开始:“Java”。看看会发生什么。

然后尝试一个包含两个条目的列表:“Java Coding”。看看在这种情况下会发生什么。

找出简单情况下发生的情况，然后处理更复杂的情况。