Removing "links" from a LinkedList?

Question

I have a LinkedList (Own code for the LinkedList) with char's in it. This is the complete list: ['a','b','I','d','R','A','7','p'].

I am trying to write a method which will deleting all characters that is NOT a upper case letter. After running the method, the LinkedList should look like this ['I','R','A'].

But after running my code I get the same list as return, this list: ['a','b','I','d','R','A','7','p'].

Here is my code for the method:

public static ListNode copyUpperCase(ListNode head) {
 ListNode ptr = head;
 while(!isEmpty(ptr.next)){
 if(!Character.isUpperCase(ptr.element)){
 ptr = ptr.next.next;
 //System.out.println(ptr.element);
 }
 ptr = ptr.next;
 }
 return head;
}

Here is isEmpty():

public static boolean isEmpty(ListNode l) {
 if ( l == null )
 throw new ListsException("Lists: null passed to isEmpty");
 return l.next == null;
}

Here is ListNode:

public class ListNode {
 public char element;
 public ListNode next;
}

I can see that the search part is working, but I can't get the deleting the node part right, any suggestions?

Answer 1

public static ListNode copyUpperCase(ListNode head) {
 ListNode ptr = head;
 while(!isEmpty(ptr.next)){
 if(!Character.isUpperCase(ptr.element)){
 ptr.next = ptr.next.next;
 //System.out.println(ptr.element);
 }
 ptr = ptr.next;
 }
 return head;
}

You need to "CHANGE" the list, so you just missed the assignment to the element and not the the local variable

THIS code will not work however, as this just assign to the next element, without looking if next element actully is a good one, and then skips to that one

Edit: full working code

class ListNode {
 public ListNode(char element,ListNode next ) {
 this.element = element;
 this.next = next;
 }
 public char element;
 public ListNode next;
 void print() {
 System.out.print(this.element+",");
 if(this.next != null) {
 this.next.print();
 }
 else {
 System.out.println("");
 }
 }
}
public class main {
 //Imo you should only check if this elem is a null one, as a null means empty, a null on next only means that it's the last elem, but will still contain data
 public static boolean isEmpty(ListNode l) {
 return l == null;
 }
 public static ListNode getNextUpper(ListNode head) {
 while(!isEmpty(head)){
 if(Character.isUpperCase(head.element)) {
 return head;
 }
 head = head.next;
 }
 return null;
 }
 public static ListNode copyUpperCase(ListNode head) {
 ListNode newhead = getNextUpper(head);
 ListNode temp = newhead;
 while(!isEmpty(temp)){
 temp.next = getNextUpper(temp.next);
 temp = temp.next;
 }
 return newhead;
 }
 public static void main(String[] args) {
 ListNode t = new ListNode('a' , new ListNode('b' , new ListNode('I', new ListNode('d', new ListNode('R', new ListNode('A', new ListNode('7', new ListNode('p',null))))))));
 t.print();
 ListNode newt = copyUpperCase(t);
 newt.print();
 }
}

• CJR: I can't get it to work, it throws exception, "null passed" at this line: while(!isEmpty(temp)){ in copperUpperCase method :(
• user3252497: I changed the isEmpty in my code, do you use that one?
• CJR: I tried it now, but I still got "java.lang.NullPointerException", and I am not allowed to change the isEmpty() method , since it's a school assignment. Do you have any suggestions how to not get the exception, I tried but it messed up the result.

Answer 2

ptr is a local variable, so

ptr = ptr.next.next;

doesn't modify your linked list.

You should modify ptr.next instead. Besides that, you may have to modify head, if the original head doesn't refer to an upper case letter.

Something like this should work :

// find the first valid (upper case) element and set head to refer to it
while (!Character.isUpperCase(head.element) && head != null)
 head = head.next;
ListNode ptr = head; 
if (ptr != null)
 // eliminate all non-upper case elements
 while(!isEmpty(ptr.next)){
 if(!Character.isUpperCase(ptr.next.element)){
 ptr.next = ptr.next.next;
 }
 ptr = ptr.next;
 }
}
return head;

• CJR: I tried that, I get the result ['R','A','p'], so it seems it skips the first uppercase character and also doesnt delete the last character, ill try to modify your code to get it working.
• CJR: Forgot to mention, I got exception error as "null lists passed", changed "while(!isEmpty(ptr.next)" to "while(!isEmpty(ptr))" and now I get the ['R','A','p'] result.