Delete Even Number of Nodes in Linked List And Print in Reverse

Question

What should be the logic followed for this scenario.

I have a linear linked list. I want to print the list in reverse order starting from the second last node.. but while removing even number of nodes. For example: 34(Node 1- Odd), 65(Node 2 - even), 733(Node 3 - odd), 34(Node 4 - even), 56(Node 5 - odd), 33(Node 6 - even)..

Now, I want output like this.. 56 (Second last node), 733(Node 4 is removed being even and it is printed cz it is odd), 34(Again even removed, odd printed in reverse form) .. and so on.

Please tell me if I have not cleared my question. And help me with the logic. Thanks

Updated

// Task A
public class LinkedList {

    protected class NodeReference {
        int info;
        NodeReference next;
        public NodeReference pLoc;
    }

    NodeReference headRef,pLoc, Loc; 
    int totalElements;
    private NodeReference next; 

    public LinkedList() {
        totalElements = 0;
        headRef = null;
    }

    public void insertAtFront(int value) {
        NodeReference newNode = new NodeReference();
                newNode.info = value;
                newNode.next = headRef;
                headRef = newNode;
    }
// Task B
    public void printList(){
        NodeReference location = headRef;
        if(headRef!=null) {
             System.out.println("The list is being printed...."); 
             while(location != null) {
             System.out.println(location.info);
             location = location.next; 
             }

        } // if block ends
        else
            System.out.println("Sorry, List is Empty!");
    }   
// Task C
    public NodeReference reverseList(NodeReference headRef) {
        if(headRef==null || headRef.next == null) 
            return headRef;

        NodeReference pLoc1 = headRef;
        NodeReference pLoc2 = headRef.next;

        headRef.next = null;
        while(pLoc1!= null || pLoc2!= null){
            NodeReference tempRef = pLoc2.next;
            pLoc2.next = pLoc1;
            pLoc1 = pLoc2;
            if (tempRef != null){
                pLoc2 = tempRef;
            }else{
                break;
            }
        }

        return pLoc2;
    }
    public void reverse() {
        reverseList(headRef);
    }
// Task D 
    public void deleteEven() {
        Loc = headRef; pLoc = null;
        while (Loc != null) {
            Loc = (Loc.next).next;
            System.out.println(Loc.info); 

        }
    }
}

Driver Program

public class LinkedListDriver {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkedList l = new LinkedList();
        l.insertAtFront(4); l.insertAtFront(7); 
        l.insertAtFront(3); l.insertAtFront(2);
        l.insertAtFront(8); l.insertAtFront(4);
        l.insertAtFront(6);
        l.printList(); 
        System.out.println("Printing Just Odd Values While Deleting Evens");
        try { 
            l.deleteEven();
        } catch(Exception e) {
            System.out.println(" End of the List..");

        }



    }

}

Answer 1

The deleteEven method was almost good but you actually skip the first element.

Also, you declare those attributes that are used only in deleteEven method and should therefore be local variables, not class attributes :

NodeReference headRef // Useless -> ,pLoc, Loc;

I have re-written deleteEven like this :

public void deleteEven() {
  NodeReference loc = headRef;
  while(loc != null && loc.next != null) {
    loc.next = loc.next.next;
    loc = loc.next;
  }
}

And also changed the main method a bit :

public static void main(String[] args) {
    LinkedList l = new LinkedList();
    l.insertAtFront(4);
    l.insertAtFront(7);
    l.insertAtFront(3);
    l.insertAtFront(2);
    l.insertAtFront(8);
    l.insertAtFront(4);
    l.insertAtFront(6);
    l.printList(); 
    System.out.println("Deleting Evens");
    l.deleteEven();
    l.printList();
}

Output :

The list is being printed....
6
4
8
2
3
7
4
Deleting Evens
The list is being printed....
6
8
3
4

Now, you have to implement the reverseList method.

Hint : the list can be double-linked (each node keeps a reference to the previous and next node). It will then be easier to keep a reference to the last element of the list and iterate from it.