removing even indexes' values in a linked list

Question

i'm writing a method removeEvens that removes the values in even-numbered indexes from a list, returning a new list containing those values in their original order. The deal is that i'm implementing my own linked list, i cannot use the LinkedList from java.util.

For example, if a variable list1 stores these values:

**list1: [8, 13, 17, 4, 9, 12, 98, 41, 7, 23, 0, 92]**
And the following call is made:

**LinkedIntList list2 = list1.removeEvens();** 
After the call, list1 and list2 should store the following values:

**list1: [13, 4, 12, 41, 23, 92]
list2: [8, 17, 9, 98, 7, 0]**

the method is in this linked list class:

public class LinkedIntList {
    private ListNode front;   // null for an empty list
    ...
}

Fields from ListNode class:

public int data;          // data stored in this node
public ListNode next;     // link to next node in the list

My code (UPDATED):

public LinkedIntList removeEvens(){
    LinkedIntList b = new LinkedIntList();
    b.front = front;
    if(front == null) {  
        System.out.println("The list inputed it empty");
    }
    else {   
        ListNode even = b.front;
        while(even!=null && even.next!=null ) { 
            int toBeAdded = even.next.data;
            even.next = even.next.next;
            add(toBeAdded);
            even = even.next;
        }
    }
    return b;
}

My output:

UPDATED OUTPUT:

It seems like i have stored the values of even-numbered indexes in a new list (list2), but how do i store the remaining values (of odd-numbered indexes) in the original list (list1)?

Answer 1

I assume you have addTail() in your LinkedIntList class to add a new node at the end of the list.

Your code would look something like this. Haven't tried it but it should work.

public LinkedIntList removeEvens(){
    LinkedIntList b = new LinkedIntList();

    if(front == null) {  
        System.out.println("The list inputed it empty");
    }
    else {   
        ListNode current = front.next; // current node always points to an odd node
        b.addTail(front); // add first node (even) to list
        front = current: // front now points to first odd node.

        // while there is odd node and the next node (even node) is not null
        while(current!=null && current.next != null) { // need to remove even node
                ListNode toBeAdded = current.next; // save the node to be removed
                current.next = current.next.next;
                b.addTail(toBeAdded);
                current = current.next;
        }
    }

    size -= b.size(); // new list size is old list size minus total removed nodes.
    return b;
}

Answer 2

One way to go about this would be to return a List of type LinkedIntList, and then just return the two lists (one for odd, one for even) in that sort of a two-dimensional fashion, like so:

public List<LinkedIntList> removeEvens(){
    List<LinkedIntList> 2dOutput = new ArrayList<>();
    LinkedIntList odd  = new LinkedIntList();
    LinkedIntList even = new LinkedIntList();
    ListNode temp = front;
    even.front=temp;
    if(front == null) {  
        System.out.println("The list inputed is empty");
    }else if(front.next == null){
        odd.front = null;
        front = null;
    }else {

        ListNode current =front.next;
        odd.front = current;
        while(temp != null){
            current.next = current.next.next;
            current = current.next;

            temp.next = temp.next.next;        
            temp = temp.next;          
        }
    }
    2dOutput.add(even);
    2dOutput.add(odd);
    return 2dOutput;
}

It's worth noting, I haven't tested this, but I'm pretty sure that will separate out the two successfully.

I'm not sure what the output field there is you posted at the end, so whatever it is may want you to format it a bit differently.

Good luck!

Answer 3

You need to change the links between the elements in your nodes and make sure that the first element in the 'odd number' list is different to the the first element in the even number list.

Initially you have:

1 -> 2 -> 3 -> 4

To have two separate lists of nodes you need to:

1. Maintain references to both node 1 and 2
2. Update the links such that 1->3 and 2->4

Answer 4

This is tested code of your problem. Here when u call remove evens. a list will contain only evens while new list b will contain only odd numbers

public class LinkedIntList { private ListNode front;

public LinkedIntList removeEvens()
    {
        LinkedIntList b = new LinkedIntList();
        ListNode temp = front;
        int count=0;

        ListNode evenPrev=null;
        ListNode oddLast=null;


        while(temp!=null)
        {

        if(count%2==0)
        {
            evenPrev=temp;
            temp=temp.next;
        }
        else
        {
                    if(oddLast==null)
                {
                b.front=temp;
                oddLast=temp;   
            }
            else
            {
                oddLast.next=temp;
                oddLast=oddLast.next;
            }

            evenPrev.next=temp.next;
            temp=temp.next;
            oddLast.next=null;      
        }
                count++;
    }
    return b;
}

public void display()
{
        ListNode temp=front;
        while(temp!=null)
        {
            System.out.println(temp.data);
            temp=temp.next;
        }
}


    public static void main(String []args)
{      
        LinkedIntList a=new LinkedIntList();
        ListNode aLast=null;

        for(int i=0;i<11;i++)
        {
                ListNode temp=new ListNode();
                temp.data=i;
                if(a.front==null)
                {
                    a.front=temp;
                    aLast=temp;
                }
                else
                {
                    aLast.next=temp;
                    aLast=aLast.next;
                }
        }

        a.display();

        LinkedIntList b=a.removeEvens();

        a.display();
        b.display();

    }

}

class ListNode { public int data; // data stored in this node public ListNode next; // link to next node in the list
}

Answer 5

Try this:

public LinkedIntList removeEvens () {
    LinkedIntList list2 = new LinkedIntList();

    for (int i = 0; i < size(); i++) {
        list2.add(get(i));
        remove(i);
    }    
    return list2;
}