Merge Sort on Strings in Java - Linked List

Question

I have an excercise in which I have to insert into a linked list a string. Suppose the String is the following:

"Java Coding Is Great"

After the Merge Sort, the linked list is supposed to look like that:

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

The problem is that in my Merge Sort code I recieve the following:

 great >> is >> java >> coding 

All the words are sorted BUT THE FIRST WORD (Head of the original list) is not.

I have two classes: TextList and WordNode.

The WordNode class has two attributes:

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

The TextList class has only one attribute: an address of the head of the linked list:

WordNode _head;

I have a constructor in which I insert the String randomly into a linked list. in the end it starts merge sotring the list. This algorithem is for this excercise.

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();
}

Merge Sort Methods: mergeSort, merge and split: (These are in the WordNode class):

Merge Sort method

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)); 
    }
}

Merge Method

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));

    }

Split Methods: one for even positions, one for odd positions.

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

Please help me figure out what's wrong. Unfortently, I can not use a third class, and I can't use pointers to the start of the list or to the end of the list.

Answer 1

Nice, but I don't like your solution to merge() in WordNode. On one hand you can compare each node you prefer to like this:

this._word.compareTo(h._word);

But in that case merge() and split() both private, so I think the better way is to put them into TextList and mergeSort() without overloading. You need to sort all nodes in linked list anytime you add a node, not just a part of it anyway. That's why this

this._head = this._head.mergeSort();

and this

public WordNode mergeSort(){
    return mergeSort(this);
}

looks useless in WordNode.
On the other hand if you put your call to mergeSort into TextList like this

this._head = this.mergeSort(this._head);

and mergeSort into this one in TextList

 public WordNode mergeSort(WordNode n){

 }

it's already better but you can do even much better by reducing more time and space compexity of the way you split your list to odds and evens like this

int counter = 1;    //  nodes counter helps to know if the current node is odd or even
WordNode L = null,  //  odd nodes
         R = null;  //  even nodes
while(h != null)
{
    if(counter%2 == 0)
        R = new WordNode(h.getWord(), R, h.getWordCounter());
    else
        L = new WordNode(h.getWord(), L, h.getWordCounter());
    //  
    h = h.getNext();
    counter++;
}

When you put it together you get something like this(don't forget words counter)

public WordNode mergeSort(WordNode h){
    int counter = 1;    //  nodes counter helps to know if the current node is odd or even
    WordNode L = null,  //  odd nodes
             R = null;  //  even nodes
    while(h != null)
    {
        if(counter%2 == 0)
            R = new WordNode(h.getWord(), R, h.getWordCounter());
        else
            L = new WordNode(h.getWord(), L, h.getWordCounter());
        //  
        h = h.getNext();
        counter++;
    }
    return merge(mergeSort(L), (mergeSort(R)));
}

what is left now is to finish merge() like this and again don't forget words counter

private WordNode merge(WordNode L, WordNode R)
{   
    while(L != null || R != null)
    {
        if(L != null && R != null)
            if(L.getWord().compareTo(R.getWord()) <= 0)
                return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
            else
                return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
        else if(L != null)
            return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
        else if(R != null)
            return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
    }
    return null;
}

say hello to proffessor Rosenstein ;-)

Answer 2

The problem here was a bit funny.

In my constructor I have carried a space with each word I have inserted to my list.

I fixed that by this code:

            s=text.substring(i+1,index);

instead of:

            s=text.substring(i,index);

The credit is to NormR from DevForum for the answer.

Answer 3

Can you use your debugger to single-step through your code? That will help you pinpoint the problem. Even a few judiciously placed breakpoints will help.

Start with a list containing only a single entry: "Java". See what happens.

Then try a two-entry list: "Java Coding". See what happens in that case.

Work out what is happening in the simple cases and then work up to the more complex ones.