javanodes

How to remove all evens in linked list java


How can I remove all the evens in a linked list in java? Other similar questions did not help me. I have a possible solution, but it seems too complicated. I'm not sure it even works.

public class Node {
public int value;
public Node next;
public Node (int val) {
    value = val;
}
public Node removeNode (Node root) {
    if (root == null || (root.next == null && isOdd(root.value))) {
        return null;
    }
    Node deep = root;
    while (deep.next != null) {
        deep = deep.next;
    }
    if (isOdd(deep.value)) {
        for (Node x = root; x != null; x = x.next) {
            if (isOdd(x.next.value)) {
                x.next = x.next.next;
            }
        }
    } else {
        for (Node x = root; x.next != null; x = x.next) {
            if (isOdd(x.next.value)) {
                x.next = x.next.next;
            }
        }
    }
    if (isOdd(root.value)) {
        root = root.next;
    }
    return root;
}
public boolean isOdd (int val) {
    return (val % 2 == 1);
}

How can I improve this solution?


Solution

  • First of all: The remove method should be in your LinkedList class, not in the Node class itself!

    After that it's quite easy to just remove the the even ones:

    public class LinkedList {
        private Node root;
    
        public void removeEvens() {
            if (root == null) return;
    
            // removing all even nodes after the root
            Node prev = root;
            while (prev.next != null) {
                if (isEven(prev.next))
                    prev.next = prev.next.next;   // next is even: delete it
                else
                    prev = prev.next;             // next is not even: proceed
            }
    
            // delete root if it's even
            if (isEven(root))
                root = root.next;
        }
    
        private boolean isEven(Node node) {
            return node.value % 2 == 0;
        }
    }