Recursively remove all occurrences of an item in a linked list

Question

public static Node deleteAll(Node front, String target){ if (front == null){ return null;} if (front.data.equals(target)){ return deleteAll(front.next,target); } front.next=deleteAll(front.next,target); return front; } 

I'm trying to get through this solution, but it bothers me. Why is this not always obtained as null, since at the end of the front it will be zero.

Answer 1

When you think about such problems, it’s nice to get a pen and paper, draw something and think about it at a high level.

For instance, ...............
Enter
List: [3] - [2] - [5] level
Goal: 2
................

First call => Result

deleteAll(N[3], 2) => [3]
but next time deleteAll(N[2], 2)
List = [3]-deleteAll(N[2], 2)

Second challenge

deleteAll(N[2], 2) => deleteAll(N[5], 2)
next node now skips 2
List = [3]-deleteAll(N[5], 2)

Third challenge

deleteAll(N[5], 2) => [5]
but the next one is now deleteAll (null, 2)
List = [3]-[5]-deleteAll(null, 2)

Lat call returns null

List ends clean without 2s
List = [3]-[5]-null

Answer 2

You have three cases:

• The original front node is null, so you are returning null.
• The original front node contains target , so you drop the front and return the result of the recursive call of the associated node.
• The original front node does not contain target , so you make a recursive call to the associated node and return front .

In number 1, you return null, and in number 3 you return a non-zero value. In number 2, you basically go again, and so return null or the next node. And so on.

This means that you can return null. But it can also return a nonzero value.