java - 将 LinkedList 节点设置为 null

Question

我之前在一本编码书籍中遇到过这个问题。

"实现一个算法删除单向链表中间的节点，给定只能访问该节点。”

书中给出的解决方案是这样的:

public static boolean deleteNode(LinkedListNode n) {
    if (n == null || n.next == null) {
        return false; // Failure
    }
    LinkedListNode next = n.next;
    n.data = next.data;
    n.data = next.data;
    n.next = next.next;
    return true;
}

这是一个很好的解决方案，当然是 O(1)。不过，这本书在最后注明了这一点。

"请注意，如果要删除的节点是最后一个节点，则无法解决此问题链表”。

我在这里遗漏了什么明显的东西吗？比方说，为什么我不能在主体之前的方法中检查 n.next 是否等于 null，如果是，就将 n 设置为 null 并返回 true？我有什么理由不能这样做吗？

Answer 1

这段代码真正做的是将下一个节点复制到给定节点中。最终效果就好像当前节点被删除了，但实际上它只是被下一个节点覆盖了。

也就是说，假设您要删除此列表中的 B:

A -> B -> C -> D

结果列表如下所示:

                 +------+
A -> B(Ccopy) ---+   C -+-> D

现在您不能对节点 D 执行此操作，因为没有要复制的下一个节点。

Why couldn't I just, say, put a check in the method before the body to check if n.next was equal to null, and if so, just set n to be null and return true? Is there any reason I can't just do that?

将 n 设置为 null 不会执行任何操作。 n 只是对要删除的列表节点的引用。如果您更改 n，您实际上并没有更改列表中的任何内容。例如，假设您想删除同一列表中的 D。它看起来像这样:

               n
               |
               v
A -> B -> C -> D

如果将n设置为null，最终结果是这样的:

               n---> null


A -> B -> C -> D

请注意，列表中的任何内容都没有发生任何变化。

在这种情况下，删除 D 的唯一方法是修改 C.next 以指向 null。也就是说，您想要这样:

              +----> null
A -> B -> C --+ D

虽然这需要修改 C，但在单向链表中，您没有简单的方法从 D 访问 C。您必须从列表的开头开始搜索，直到找到满足 x.next == D 的节点 x。