code removing wrong Nodes

Question

I am learning to manipulate Nodes, and am having an issue with one of my test cases and it seems my code is not removing the correct nodes. The code should be removing nodes that contain lowercase Characters, but when the test case expects E I get l returned. Could someone look over my code and test case and explain what is wrong. I cannot use static variables, arrays or Java collections.

my code

public class ListUppercaseExample {

    public static Node<Character> uppercase(Node<Character> head) {
        if (head == null) {
            return null;
        }
        Node<Character> prev = head;
        Node<Character> start = head;

        while (head != null) {
            if (Character.isLowerCase(head.value)) {
                if (Character.isLowerCase(start.value)) {
                    start = head.next;
                    prev = head.next;
                    head = head.next;
                } else {
                    if(head.next == null){
                        return start;
                    }
                    else{
                        prev.next = head.next;
                        head = head.next;
                    }
                }
            } else {
                head = head.next;
            }
        }

        return start;
    }
}

my node class

public final class Node<T> {
    public final T value;
    public Node<T> next;

    public Node(T _value) {
        this( _value, null );
    }

    public Node(T _value, Node<T> _next) {
        value = _value;
        next  = _next;
    }

    @Override
    public String toString() {
        return "" + value;
    }
}

test case

@Test
public void testDrEvil() {
    @SuppressWarnings("unchecked")
    Node<Character>[] nodes = new Node[] { 
        new Node<Character>( 'd' ), // 0
        new Node<Character>( 'R' ), // 1
        new Node<Character>( 'E' ), // 2
        new Node<Character>( 'v' ), // 3
        new Node<Character>( 'I' ), // 4
        new Node<Character>( 'l', null )
    };

    for (int i = 0; i < nodes.length-1; i++) {
        nodes[ i ].next = nodes[ i+1 ];
    }

    // expected: D -> R
    Node<Character> actual = ListUppercaseExample.uppercase(nodes[0]);
    Node<Character> now = actual;
    assertEquals("", nodes[1], now); // R
    assertEquals("", nodes[2], now.next); // E
    now = now.next;
    assertEquals("", nodes[4], now.next); // I
    now = now.next;
    assertEquals("", null, now.next);
}

Answer 1

You have two problems:

1. You are not removing the last value in the list if the last value is lowercase because of this line in your while loop:

   if(head.next == null){
       return start;
   }
   

   You want to skip over the current value of head if it is lowercase, whether the next value is null or not. So you can just remove that part of the if-statement so your code is like this:

   if (Character.isLowerCase(start.value)) {
       start = head.next;
       prev = head.next;
       head = head.next;
   } else {
       prev.next = head.next;
       head = head.next;
   }
   

2. You are never updating prev. You need to set prev to head when the character is an uppercase before you change the value of head. Your else statement if character is uppercase should look like like this:

   } else {
       prev = head;
       head = head.next;
   }
   

Once those changes are made, your while loop should look like:

  while (head != null) {
        if (Character.isLowerCase(head.value)) {
            if (Character.isLowerCase(start.value)) {
                start = head.next;
                prev = head.next;
                head = head.next;
            } else {
                prev.next = head.next;
                head = head.next;
            }
        } else {
            prev = head;
            head = head.next;
        }
    }