递归删除链表中所有特定元素

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;
}

我正在尝试理解这个解决方案，但它让我感到困惑。为什么它不总是结果为null，因为最后front将等于null。

- dogkid45

---

它从第一个函数调用返回结果。 - JoshKisb

Answer 1

当思考这些问题时，拿出笔和纸，在高层次上画一些东西并思考一下是个好主意。

例如
...............
输入
列表：[3]-[2]-[5]-null
目标：2
................

第一次调用 => 结果

deleteAll(N[3], 2) => [3]
但下一步是 deleteAll(N[2], 2)
List = [3]-deleteAll(N[2], 2)

第二次调用

deleteAll(N[2], 2) => deleteAll(N[5], 2)
接下来的节点现在跳过了 2
List = [3]-deleteAll(N[5], 2)

第三次调用

deleteAll(N[5], 2) => [5]
但下一步是 deleteAll(null, 2)
List = [3]-[5]-deleteAll(null, 2)

最后一次调用返回 null

列表最终没有 2
List = [3]-[5]-null

- JoshKisb

Answer 2

你有三种情况：

1. 原始的 front 节点为空，因此返回 null。
2. 原始的 front 节点持有 target，因此丢弃 front 并返回链接节点上递归调用的结果。
3. 原始的 front 节点不持有 target，因此在链接节点上执行递归调用并返回 front。

在第一种情况下，你返回 null，在第三种情况下，你返回非 null。在第二种情况下，你基本上再次进行，因此返回 null 或下一个节点。等等。

这意味着可能返回 null。但也可能返回非 null。

- Ben P.