java - 当您只能访问该节点时，如何删除链表中的节点

Question

我的理解是，为了删除单链表中的节点，我们需要访问当前节点和前一个节点。我有以下逻辑:

public SingleNode delete(int val) {

    SingleNode current = head;
    SingleNode prev = head;

    while(current.data != val) {

        if (current.next == null) {
            return null;
        } else {
            prev = current;
            current = current.next;
        }

    }

    if(current == head) {
        head = current.next;
    } else {
        prev.next = current.next;
    }

    return current;

}

当您只能访问当前节点时，如何更改代码以便可以删除链表中的节点？

Answer 1

How can I change the code so that I can delete a node in linked list when you are given access to only the current node?

对于单链表，您无法删除具有给定引用的节点，除非您有前一个节点，或者您可以访问列表的头部.

如果你有头，你可以在 O(N) 步内找到前一个节点。

有一种通过修改节点来删除节点的方法，该方法在大多数情况下都有效，但有多种边缘情况使其变得困难。 (如果您需要支持并发删除和迭代等，它肯定不起作用。)