实现整数单链表时，定位指定值并删除节点的最高效方法是什么？

首先，先聊聊你当前实现的remove方法存在的几个问题——这些问题不仅会导致运行错误，还影响了执行效率：

• 空指针异常风险：当遍历到链表最后一个节点时，iterator.next为null，此时访问iterator.next.data会直接抛出NullPointerException。
• 遗漏头节点的处理：如果头节点的data正好是要删除的value，你的方法完全不会处理这种情况，因为它只检查iterator.next的节点值。
• 不必要的遍历：如果只需要删除第一个匹配的节点，当前方法会遍历完整个链表，浪费了不必要的时间。

下面我会给出两种常见场景下的高效实现：删除第一个匹配值的节点和删除所有匹配值的节点，同时解决上述问题。

一、删除第一个匹配值的节点（最高效，找到即停止） #

这种场景下，我们找到第一个匹配的节点后就立即停止遍历，时间复杂度最优为O(1)（头节点就是目标），最坏为O(n)。

public void removeFirst(int value) {
    // 处理头节点就是目标的情况
    if (head != null && head.data == value) {
        head = head.next;
        return;
    }

    Node current = head;
    // 遍历寻找目标节点的前驱节点，同时避免空指针
    while (current != null && current.next != null) {
        if (current.next.data == value) {
            // 跳过目标节点，完成删除
            current.next = current.next.next;
            return; // 找到第一个就停止，提升效率
        }
        current = current.next;
    }
}

二、删除所有匹配值的节点 #

如果需要删除链表中所有等于目标值的节点，我们需要完整遍历链表，但也要正确处理头节点和连续匹配的情况：

public void removeAll(int value) {
    // 先处理头部连续的目标节点
    while (head != null && head.data == value) {
        head = head.next;
    }

    if (head == null) {
        return; // 链表已经为空，直接返回
    }

    Node current = head;
    while (current.next != null) {
        if (current.next.data == value) {
            // 跳过目标节点
            current.next = current.next.next;
        } else {
            // 只有当前节点的下一个不是目标时，才移动指针
            current = current.next;
        }
    }
}

更简洁的优化：使用哨兵节点（Dummy Node） #

如果不想单独处理头节点的特殊情况，可以用一个哨兵节点作为临时头，这样所有节点的处理逻辑可以统一，代码更简洁不易出错：

public void removeFirstWithDummy(int value) {
    Node dummy = new Node();
    dummy.next = head;
    Node current = dummy;

    while (current.next != null) {
        if (current.next.data == value) {
            current.next = current.next.next;
            break; // 删除第一个就停止
        }
        current = current.next;
    }

    // 更新原链表的头节点
    head = dummy.next;
}

效率说明 #

不管哪种实现，时间复杂度都是O(n)（最坏情况需要遍历整个链表），但我们通过找到目标后立即停止（针对删除第一个的场景）、避免空指针检查冗余等方式，让实际运行效率达到最优。空间复杂度都是O(1)，因为只用到了常数个额外指针。

最后给你的display方法提个小建议：方法参数里的LinkedList list其实是多余的，你可以直接访问当前对象的head节点，修改后更简洁：

public void display() {
    Node iterator = head;
    while (iterator != null) {
        System.out.println(iterator.data);
        iterator = iterator.next;
    }
}

内容的提问来源于stack exchange，提问作者user11149483