LeetCode移除链表元素：覆盖节点后断开无效问题求助

问题出在哪？ #

你的代码有两个核心问题，导致多余节点无法被正确断开：

1. 断开节点的对象完全错了 #

拿你举的例子来说：原链表是1->2->3->4->5，val=3，收集到的有效数值列表是[1,2,4,5]（长度4）。
在覆盖节点的循环里，你是先给当前current赋值，再把current移到下一个节点。4次循环结束后，current已经跑到了原链表的第5个节点（也就是那个多余的、值为5的节点）。这时候你执行current.next = null根本没用——这个节点的next本来就是null，而真正需要切断的是第4个节点（最后一个要保留的节点）的next指针，让它不再指向这个多余节点。

2. 没处理全节点都要移除的情况 #

如果原链表所有节点的值都等于val，那收集到的列表是空的。这时候current还是初始的head，直接执行current.next = null会触发空指针异常，而且最终返回的head也不符合要求（题目要求返回null）。

修复后的代码 #

针对上面的问题，调整后的代码如下：

public ListNode removeElements(ListNode head, int val) {
    // 收集需要保留的节点值
    List<Integer> list = new ArrayList<>();
    ListNode current = head;
    while (current != null) {
        if (current.val != val) {
            list.add(current.val);
        }
        current = current.next;
    }

    // 所有节点都要移除，直接返回null
    if (list.isEmpty()) {
        return null;
    }

    // 覆盖原链表的节点值，停在最后一个要保留的节点上
    current = head;
    for (int i = 0; i < list.size(); i++) {
        current.val = list.get(i);
        // 只有不是最后一个保留节点时，才移动指针
        if (i != list.size() - 1) {
            current = current.next;
        }
    }

    // 切断最后一个保留节点和后续多余节点的联系
    current.next = null;
    return head;
}

修复逻辑说明 #

• 加了空列表判断，直接返回null，符合题目要求
• 修改了覆盖循环的逻辑：遍历到最后一个要保留的节点时，不再移动current，此时current正好指向要保留的最后一个节点，执行current.next = null就能彻底切断多余节点的连接

额外提一句 #

虽然这种覆盖值的方法能得到正确结果，但和题目要求的「移除节点」逻辑不符，还额外占用了ArrayList的内存空间。最优解法还是直接操作链表指针移除节点，空间复杂度是O(1)，比如用虚拟头节点的写法：

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode current = dummy;
    while (current.next != null) {
        if (current.next.val == val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return dummy.next;
}

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