CODEWITHSUNDEEP
javarecursionlinked-list
dogkid45
dogkid45

Reputation: 53

Recursively remove all occurrences of an item in a linked list

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 walk through this solution, but it is confusing me. Why doesn't it always result as null since at the end front will equal null.

Upvotes: 5

Views: 1446

Answers (2)

JoshKisb
JoshKisb

Reputation: 752

When thinking about such problems it is a good idea to get a pen and paper and draw some stuff and think about it on a high level

For example
...............
Input
List: [3]-[2]-[5]-null
Target: 2
................

First call => Result

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

Second call

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

Third call

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

Lat call returns null

List ends up clean with no 2s
List = [3]-[5]-null

Upvotes: 3

Ben P.
Ben P.

Reputation: 54204

You have three cases:

  1. The original front node is null, so you return null.
  2. The original front node holds target, so you discard front and return the result of the recursive call on the linked node.
  3. The original front node does not hold target, so you perform the recursive call on the linked node and return front.

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

This means it's possible to return null. But it's also possible to return non-null.

Upvotes: 0

Related Questions