从链接列表中删除元素

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与pointer.next一起移动，那么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！