Recursive Linked List method: RemoveAll

[cjw92]

The problem is: Remove all occurrences of a value from a linked list recursively.

The method header is: private static Node removeAll(Node head, String value)

Node head is the head of the list, String value is the value to be checked for removal.

The code I have so far is:

private static Node removeAll(Node head, String value)
{
if(head == null) return null;
if(head.next == null)
{
if(head.value.equals(value))
return null;
else return head;
}
else
{
Node probe = head;
if (probe.value.equals(value))
{
head = head.next;
return removeAll(probe.next, value);
}
else
{
return removeAll(probe.next, value);
}
}
}

I think the right way to do this is that probe is supposed to find the spot to remove, and then I do head = head.next to actually remove it from the list. However, I am removing all elements but the last one when I run it. If anyone could tell me what I'm doing wrong I would appreciate it. Thanks.

[Junky]

You are making it much harder than it needs to be. Here is one stategy:

removeAll(Node head, String value) {
    if(head != null) {
        removeAll(head.next, value); // recursion all the way to the tail
        // delete nodes on the way back up
        if(....) {
            // delete node
        }
    }
}

[cjw92]

You are making it much harder than it needs to be. Here is one stategy:

removeAll(Node head, String value) {
    if(head != null) {
        removeAll(head.next, value); // recursion all the way to the tail
        // delete nodes on the way back up
        if(....) {
            // delete node
        }
    }
}

I don't understand how that would work, is the if(...) statement

if(head.value.equals(value))
{
head = head.next;
return removeAll(head.next, value);
}

[Junky]

Is the list single or double linked? The pseudocode I provided is for a double linked list.

[cjw92]

Is the list single or double linked? The pseudocode I provided is for a double linked list.

Oh that makes so much more sense now. Yeah I did not know there were double linked list, so is that the standard? And yeah it is a single linked list.

[Junky]

Since you have a single LinkedList what you have to do is build up a new List with the undesired Nodes omiitted.

Lets say we have the following list: 1,9,2,9,3 and we want to remove all the 9's. Your recursion takes you all the way to the tail, ie the 3 node. Since there are no more node you return the current node (3 node). Your recursion goes back one level to the 9 node. Since this is a node you want to omit just return the node you got from the recursive call (ie the 3 node). Now go back another level to the 2 node. You return the current node PLUS the node you got from the recursive call (ie the 3 node). Back another level to the 9 node which you want to omit etc etc