覆盖和删除链表元素

Question

我正在解决以下leetcode问题，其中给定一个链表，你应该删除所有具有特定值val的ListNode。

我知道最好的解决方案是直接从列表中删除节点，但我尝试了不同的方法：

public ListNode removeElements(ListNode head, int val) {
    // copy wanted values from linkedlist into list
    List<Integer> list = new ArrayList<>();
    ListNode current = head;
    while (current != null){
        if (current.val != val){
            list.add(current.val);
        }
        current = current.next;
    } 

    // overwrite the values of the first few nodes
    current = head;
    for(Integer num : list){
        current.val = num;
        current = current.next;
    }

    // disconnect the last node from the remaining ones
    current.next = null;
    return head;
}

例如，如果列表 (1 -> 2 -> 3 -> 4 -> 5) 给出 val=3： 首先，我保存所有不是 3 的值。然后我覆盖相同的列表 (1 -> 2 -> 4 -> 5 -> 5)，然后删除指向剩余节点的指针 (1 -> 2 - > 4 -> 5).

我知道问题要求删除节点而不是覆盖它们，但由于我不应该就地解决，所以我认为这应该不重要。

但这不起作用：第一个节点总是正确的，但原始列表中几乎总是有应该断开连接的节点。我不知道为什么将最后一个指针设置为 null 并不能消除它们。

我知道这不是你应该解决这个问题的方式，但我不明白为什么它不应该这样工作。

Answer 1

但这不起作用：第一个节点总是正确的，但原始列表中几乎总是有应该断开连接的节点。我不知道为什么将最后一个指针设置为 null 并不能消除它们。

你真的应该学习使用调试器。它是了解程序中实际情况的宝贵工具。如果您使用 IDE，那么它肯定有一个集成的。

或者，如果您想分析代码而不运行它，那么从非常简单的情况开始。例如，

• 空列表
• 单个元素列表
  • 需要删除元素的地方
  • 不需要移除的地方
• 等等。

让我们考虑一下空列表的情况，我假设它是通过作为

head

传入的

null

来传达的。您的代码将成功地将所有零元素的值提取到

list

中，但是看看当您将这些值写回时会发生什么（注释作为注释添加）：

    current = head;  // 'head' is null, so this is equivalent to current = null;

    for(Integer num : list){ // 'list' is empty, so no iterations are performed
        current.val = num;
        current = current.next;
    }

    // disconnect the last node from the remaining ones
    current.next = null;  // 'current' is still  null, so kapow! NullPointerException

如果问题的性质尚不清楚，那至少应该告诉您，当您截断列表时，它与

current

有关。我相信，稍加思考，您就会认识到

current

始终指的是 after 所有已被接受保留在列表中的节点。它是需要截断的第一个，而不是需要保留的最后一个，并且分配

current.next = null

不会截断它。 （也不会

current = null

。你必须比那更聪明。）

实际解决方案留作练习。