#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    25
    Rep Power
    0

    Merge Sort a linked list in java


    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:

    Code:
    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.

    Code:
    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
    Code:
    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
    Code:
    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.
    Code:
    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.
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    Can you post complete code that complies, executes and shows the problem?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    25
    Rep Power
    0
    Originally Posted by NormR
    Can you post complete code that complies, executes and shows the problem?
    Thank you, this is the complete code:

    Code:
    public class TextList {
    	private WordNode _head;
    	public TextList(){
    		_head=null;
    	}
    	/**
    	 * 
    	 * @param text - a senctence to enter the list.
    	 */
    	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, 
    			//so 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);
    			}
    		}
    		
    		_head=this._head.mergeSort();
    		//addLastWord();
    				
    	}
    	
    
    	public String toString(){
    		String res=""; WordNode ptr=_head;
    		do{
    			res=res + ptr.getWord() + " ";
    			ptr=ptr.getNext();
    		}while (ptr!=null);
    		return res;
    	}
    	//retrive last word and put it the first node to final sort
    	private void addLastWord(){
    		WordNode ptr=_head;
    		while (ptr!=null){
    			if (ptr.getNext().getNext()==null){
    				addToData(ptr.getNext().getWord());
    				ptr.setNext(null);
    				break;
    			}
    			else
    				ptr=ptr.getNext();
    		}
    	}
    		public void addToData(String word)
    		{
    			WordNode temp=null;
    		
    			//not a legal string
    			if (word.charAt(0)<'a' || word.charAt(0)>'z')
    				System.out.println("illegal word");
    			//if list is empty
    			if (_head==null)
    				this._head=new WordNode(word,null);
    			else
    			{
    				WordNode ptr=_head;
    				/*//if (ptr.getWord().compareTo(word)>0){
    					temp=new WordNode (word,_head);
    					_head=temp;
    				}//*/
    				//while the current node's work is smaller than the argument word
    				if (ptr.getWord().compareTo(word)<0){
    					temp=new WordNode(word,_head);
    					_head=temp;
    				}
    				while (ptr.getNext()!=null && ptr.getNext().getWord().compareTo(word)<0)
    					ptr=ptr.getNext();
    				//increment counter if word is equal to the node's word
    				if (word.compareTo(ptr.getWord())==0)
    					ptr.setCounter();
    				else{
    					 temp=new WordNode (word,ptr.getNext());
    					 ptr.setNext(temp);
    				}
    				
    				
    			}
    			
    		}
    		
    			 
    		
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String s="anything you can do";
    		TextList t=new TextList(s);
    		System.out.println(t.toString());
    		
    		
    	}
    
    }
    WordNode Class:

    Code:
     */
    public class WordNode {
        private String _word;
        private WordNode _next;
        private int _wordCount;
         /**
          * 
          * @param w - a word to enter the node
          * @param n - node to point next
          */
        public WordNode(String w, WordNode n){
            _word=w;
            _next=n;
            _wordCount=1;
        }
        /**
         * get method to get the node the current node points to
         * @return WordNode next node in the list
         */
        public WordNode getNext(){
            return _next;
        }
        /**
         * get the word of the current node
         * @return String of the word of the current node
         */
        public String getWord(){
            return _word;
        }
        /**
         * get the number of times the word appears in the list
         * @return int number of times in the list
         */
        public int getCount(){
            return _wordCount;
        }
        /**
         * changes the pointer next
         * @param n WordNode to point to
         */
        public void setNext(WordNode n){
            _next=n;
        }
        /**
         * changes the String value in the current node.
         * @param word String to assign
         */
        
        public void setWord(String word){
            _word=word;
        }
        public void setCounter(){
            this._wordCount++;
        }
        /**
         * merge sorts the nodes
         * @return a merged list nodes
         */
        public WordNode mergeSort(){
    	    	return mergeSort(this);
    	    	
    	    }
        
        public WordNode mergeSort(WordNode h){
            // Sort h by recursively splitting and merging
            if (h==null || h._next==null)
                return h;
            else{
                WordNode odds=h.splitOdds();
                WordNode evens=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));
                
            }
            
        
        //MUST BE INITILIZED ON HEAD
        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;
            }
            
            
        public String toString(){
            String res=""; WordNode ptr=this;
            while (ptr!=null){
                System.out.print(ptr._word + " " );
                ptr=ptr.getNext();
            }
            System.out.println(res);
            return res;
        }
        
            
        public static void main(String[] args) {
    
            
        }
    
    }

    THE RESULT:
    can do you anything
    insted of
    anything can do you

    THANK YOU
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    Try doing some debugging by adding println() statements that print out the values used in the code.

    The first thing I saw when I executed the code was a leading space.
    The following was printed:
    Code:
    > can  do  you anything <
    012345678901234567890
    with this statement:
    Code:
    		System.out.println(">"+t.toString()+"<");
    The numbers were added here to show the spaces.

    Hint: a space is less than any letter

    Comments on this post

    • nerazzurri10 agrees : Thank you.
    Last edited by NormR; June 8th, 2013 at 01:04 PM.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    25
    Rep Power
    0
    So you're saying that each of my nodes has a space before the first letter and it leads to problems?

    Thank you for helping.

    Edit:

    Your hypotises is true (and brilliant). in my constructor I have taken spaces with me in every String. Now, it seems to work.


IMN logo majestic logo threadwatch logo seochat tools logo