从链表中移除元素

Question

def removeKFromList(l, k):
    
    pointer = l
    while pointer:
        if pointer.next and pointer.next.value == k:
            pointer.next = pointer.next.next
        else:
            pointer = pointer.next
    
    if l and l.value == k:
        return l.next
    else:
        return l

在这段代码中，为什么我需要放 pointer = pointer.next 在其他？如果我不在 else 下编写代码，代码将无法运行，但我不明白为什么。

Answer 1

首先意识到 pointer 旨在引用在之前可能需要删除的节点。

现在如果我们发现必须删除 pointer 的后继者，那么我们进入 if 块。在那种情况下，删除下一个节点将使 在那个 之后的节点成为 pointer 的新继承者。由于我们还想为那个新的继任者进行检查（删除），我们应该 而不是 移动 pointer，但就这样吧。在下一次迭代中，我们将正确判断是否必须删除新的后继节点。

如果我们用 pointer.next 移动 pointer，那么 pointer 将引用新的继任者，但不会检查是否删除（在下一次迭代中）。它会逃过移除检查！

这是我们在这种情况下 pointer = pointer.next 时可能出错的可视化。

输入：l = [1,2,2,3], k = 2

  l
pointer
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 2  │    │ value: 3  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘

在第一次迭代中条件pointer.next.value == k为真，所以用pointer.next = pointer.next.next进行移除，导致这种情况：

  l
pointer
  ↓           ┌────────────────┐ 
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐    ┌───────────┐
│ value: 1  │ │  │ value: 2  │ └> │ value: 2  │    │ value: 3  │
│ next: ──────┘  │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘

如果现在我们做 pointer = pointer.next，那么我们得到：

  l                                pointer
  ↓           ┌────────────────┐    ↓
┌───────────┐ │  ┌───────────┐ │  ┌───────────┐    ┌───────────┐
│ value: 1  │ │  │ value: 2  │ └> │ value: 2  │    │ value: 3  │
│ next: ──────┘  │ next: ───────> │ next: ───────> │ next:None │
└───────────┘    └───────────┘    └───────────┘    └───────────┘

...并且在下一次迭代中，if 条件将不是关于该节点，而是关于下一个值为 3 的节点，因此不会删除第二次出现的 2！

从链表中移除元素

Remove Element from the linked list

linked-list