Merge Two LinkedList

[kyriacos1986]

I have been asked to create a method to merge two LinkedList.

I am allowed to use only the following methods:

From LinkedList:
> addLast(E);
> size();

From ListIterator:
> E next();
> boolean hasNext();
> E previous();
> void remove();

The first list (list1) points to 2,6,7
The second list (list2) points to 3,5,8

--> After the creation of the merge list the two lists must be empty.

Here is my code:

Class SortedLinkedList:

import java.util.*;

public class SortedLinkedList<E extends Comparable<? super E>> extends LinkedList<E>
{
    @SuppressWarnings("unchecked")
	public void mergeLists(SortedLinkedList<E> list1, SortedLinkedList<E> list2)
    {
        ListIterator<E> itr1 = list1.listIterator(); //List Iterator for the first list
        ListIterator<E> itr2 = list2.listIterator(); //List Iterator for the second list
        
        while(itr1.hasNext() || itr2.hasNext())
        {
            E item1 = null; //variable to first node in first list
            E item2 = null; //variable to first node in second list
            
            if(itr1.hasNext())
            {
                item1 = itr1.next();
            }
            if(itr2.hasNext())
            {
                item2 = itr2.next();
            }
            if(item1 == null)
            {
                while(list2 != null)
                {
                    item1 = itr2.next();
                }
            }
            else if(item2 == null)
            {
                while(list1 != null)
                {
                    item2 = itr1.next();
                }
            }
            else if(item1.compareTo(item2) < 0)
            {
                addLast(item1);
                ((ListIterator<E>) item1).next();
                ((LinkedList<E>) item1).remove();                
            }
            else
            {
                addLast(item2);
                ((ListIterator<E>) item2).next();
                ((LinkedList<E>) item2).remove();
            }
        }
            
            
    }
}

Class TestMergeList:

import java.util.*;

public class TestMergeList
{
    public static void main(String[] args)
    {
        SortedLinkedList<Integer> list1 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> list2 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> newList = new SortedLinkedList<Integer>();
        
        list1.addLast(2);
        list1.addLast(6);
        list1.addLast(7);
        
        list2.addLast(3);
        list2.addLast(5);
        list2.addLast(8);
        
        newList.mergeLists(list1,list2);
    }
        
}

Compiler points to the following errors:

Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.util.ListIterator
	at SortedLinkedList.mergeLists(SortedLinkedList.java:41)
	at TestMergeList.main(TestMergeList.java:19)

I appreciate any help.

[teo236]

I can't understand exactly what you are trying to do. item1 and item2 are Integer types or classes. You are using templates. That's why it gives you that error. If you are trying to remove element x from a list you have to do it like this:

list.remove(x);//where x is the element to remove

In your case, if i understand it correctly, you have to replace a part of your code:

...
else if(item1.compareTo(item2) < 0)
            {
                addLast(item1);
                list1.remove(item1);//replace this!!!             
            }
            else
            {
                addLast(item2);
                list2.remove(item2);//replace this!!!       
            }
...

[kyriacos1986]

I change my code with yours and I am receiving the following:

java.util.ConcurrentModificationException
at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
at java.util.LinkedList$ListItr.next(LinkedList.java:696)
at SortedLinkedList.mergeLists(SortedLinkedList.java:25)
at TestMergeList.main(TestMergeList.java:27)

[teo236]

sorry, my mistake. This is the right code:

...
else if(item1.compareTo(item2) < 0)
            {
                addLast(item1);
                itr1.remove();       
            }
            else
            {
                addLast(item2);
                itr2.remove();       
            }
...

[kyriacos1986]

[2, 5, 7]

Ii seems that the values are interchanging between the two lists.
Any idea?

[teo236]

I need to know what do you wanted to do adding this 2 lines:

((ListIterator<E>) item1).next();
      ((LinkedList<E>) item1).remove();

[kyriacos1986]

I wanted to remove the correct item in the list so I call the next() method and then the remove() so the item that will be deleted will be the one that the iterator traversed.

[kyriacos1986]

I have update my code but the program doesn't look right as it supposed.
Could anyone help me to finish my code?
I will appreciate any help.

Here is my code so far:

SortedLinkedList class:

import java.util.*;

public class SortedLinkedList<E extends Comparable<? super E>> extends LinkedList<E>
{
    public void mergeLists(SortedLinkedList<E> list1, SortedLinkedList<E> list2)
    {
        ListIterator<E> itr1 = list1.listIterator(); //List Iterator for the first list
        ListIterator<E> itr2 = list2.listIterator(); //List Iterator for the second list
        
        while(itr1.hasNext() || itr2.hasNext())
        {
            E item1 = null; //variable to first node in first list
            E item2 = null; //variable to first node in second list
            
            if(itr1.hasNext())
            {
                item1 = itr1.next();
            }
            if(itr2.hasNext())
            {
                item2 = itr2.next();
                
            }
            if(item1 == null) // list1 is empty
            {
                return;
                
            }
            else if(item2 == null) // list2 is empty
            {
                return;
                
            }
            else if(item1.compareTo(item2) < 0)
            {
                addLast(item1);  
            }
            else
            {
                addLast(item2);
            }
        }
            
            
    }
}

TestMergeList class:

import java.util.*;

public class TestMergeList
{
    public static void main(String[] args)
    {
        SortedLinkedList<Integer> list1 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> list2 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> newList = new SortedLinkedList<Integer>();
        
        list1.addLast(2);
        list1.addLast(6);
        list1.addLast(7);
        
        list2.addLast(3);
        list2.addLast(5);
        list2.addLast(8);
        
        newList.mergeLists(list1,list2);
        System.out.println( newList );
    }
        
}

[teo236]

I think that if you have to replace this segment of code:

else if(item1.compareTo(item2) < 0)
            {
                addLast(item1);  
            }
            else
            {
                addLast(item2);
            }

with this one:

//you have to start a new 'if', don't use 'else if' any more
                if(item1.compareTo(item2) < 0){//If you want to add both items, in each 'if' you have to write both addLast() methods
                    addLast(item1);
                    addLast(item2);
                    itr1.remove();//this method from ListIterator removes the current item -> item1
                    itr2.remove();//this method from ListIterator removes the current item -> item2
                }else{//do the same thing but interchaging the order
                    addLast(item2);
                    addLast(item1);
                    itr1.remove();//this method from ListIterator removes the current item -> item1
                    itr2.remove();//this method from ListIterator removes the current item -> item2
                }

You can make your code much shorter.

[kyriacos1986]

Thanks teo for your help here is my code and works just fine:

SortedLinkedList class:

import java.util.*;

public class SortedLinkedList<E extends Comparable<? super E>> extends LinkedList<E>
{
    public void mergeLists(SortedLinkedList<E> list1, SortedLinkedList<E> list2)
    {
        ListIterator<E> itr1 = list1.listIterator(); //List Iterator for the first list
        ListIterator<E> itr2 = list2.listIterator(); //List Iterator for the second list
        
        while(itr1.hasNext() || itr2.hasNext())
        {
            E item1 = null; //variable to first node in first list
            E item2 = null; //variable to first node in second list
            
            if(itr1.hasNext())
            {
                item1 = itr1.next();
            }
            if(itr2.hasNext())
            {
                item2 = itr2.next();
                
            }
            if(item1 == null) // list1 is empty
            {
                return;
                
            }
            else if(item2 == null) // list2 is empty
            {
                return;
                
            }

            else{
                
                if(item1.compareTo(item2) < 0){//If you want to add both items, in each 'if' you have to write both addLast() methods
                    addLast(item1);
                    addLast(item2);
                    itr1.remove();//this method from ListIterator removes the current item -> item1
                    itr2.remove();//this method from ListIterator removes the current item -> item2
                }else{//do the same thing but interchaging the order
                    addLast(item2);
                    addLast(item1);
                    itr1.remove();//this method from ListIterator removes the current item -> item1
                    itr2.remove();//this method from ListIterator removes the current item -> item2
                }
            }
        }
            
        }
    
}

TestMergeList class:

public class TestMergeList
{
    public static void main(String[] args)
    {
        SortedLinkedList<Integer> list1 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> list2 = new SortedLinkedList<Integer>();
        SortedLinkedList<Integer> newList = new SortedLinkedList<Integer>();
        
        list1.addLast(2);
        list1.addLast(6);
        list1.addLast(7);
        
        list2.addLast(3);
        list2.addLast(5);
        list2.addLast(8);
        
        newList.mergeLists(list1,list2);
        System.out.println( newList );
        
        
            System.out.println( "list1 size: " + list1.size());
            System.out.println( "list2 size: " + list2.size());
    }
        
}

Output:

[2, 3, 5, 6, 7, 8]
list1 size: 0
list2 size: 0