<p><strong>基本缺陷</strong></p>
<p>试图通过迭代和变异来解决这个问题有一个基本缺陷。尽可能努力,<code>remove_elements</code><em>可以</em>调整<code>head</code>和<code>next</code>属性,但它<em>不能</em>将<code>ListNode</code>更改为<code>None</code>-</p>
<pre class="lang-py prettyprint-override"><code>w = node(1)
print(w) # ListNode { head = 1, next = None }
remove(w, 1)
print(w) # ???
</code></pre>
<p>我们希望看到<code>None</code>作为结果,但如果没有以下至少一项,这是不可能的-</p>
<ol>
<li>函数调用必须更改</li>
<li><code>ListNode</code>的数据结构必须更改</li>
</ol>
<p>假设您想要保持<code>ListNode</code>的形状,我们必须将函数调用调整为-</p>
<pre class="lang-py prettyprint-override"><code>w = node(1)
print(w)
w = remove_elements(w, 1) # <- reassign with result of call
print(w)
</code></pre>
<p>现在使用<code>remove_elements</code>的返回值,我们可以捕捉到<code>ListNode</code>降级为普通<code>None</code>的场景。用你的第一个例子-</p>
<pre class="lang-py prettyprint-override"><code>p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))
print(to_str(p))
p = remove_elements(p, 6) # <- reassign p
print(to_str(p))
</code></pre>
<pre class="lang-none prettyprint-override"><code>6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅
</code></pre>
<p>还有你的第二个例子-</p>
<pre class="lang-py prettyprint-override"><code>q = node(1, node(1))
print(to_str(q))
q = remove_elements(q, 1) # <- reassign q
print(to_str(q))
</code></pre>
<pre class="lang-none prettyprint-override"><code>1->1->∅
∅
</code></pre>
<p>下面是一个<strong>可变的</strong>单链表的实现-</p>
<pre class="lang-py prettyprint-override"><code>class node:
def __init__(self, head, next = None):
self.head = head
self.next = next
def remove_elements(t, val):
# load stack
s = []
while t:
if t.head != val:
s.append(t)
t = t.next
# unload stack
r = None
while s:
q = s.pop()
q.next = r
r = q
# return
return r
def to_str(t):
r = ""
while t:
r = r + str(t.head) + "->"
t = t.next
return r + "∅"
</code></pre>
<hr/>
<p><strong>了解你的出身</strong></p>
<p>这个问题加上了<code>recursion</code>的标签,这是理所当然的。链表是一种递归数据结构,选择一个递归程序来处理链表可以使程序的结构与数据的结构相协调。然而,递归是一种函数遗产,因此将其与函数风格结合使用会产生最好的结果。这意味着避免突变、变量重新分配和其他副作用。不销毁现有值,而是创建一个新的<em>值-</p>
<ol>
<li>如果输入列表<code>t</code>为空,则已达到基本大小写。返回空列表</li>
<li>(感应)输入为<em>非</em>空;它至少有一个元素。如果第一个元素<code>t.head</code>与要删除的值<code>val</code>匹配,则返回子问题的结果<code>t.next</code></li>
<li>(感应式)输入不为空,且第一个元素与要删除的值不匹配。构造一个新的<code>t.head</code>列表节点,子问题的结果<code>t.next</code>-</li>
</ol>
<pre class="lang-py prettyprint-override"><code>def remove_elements(t, val):
if not t:
return None # 1
elif t.head == val:
return remove_elements(t.next, val) # 2
else:
return ListNode(t.head, remove_elements(t.next, val)) # 3
</code></pre>
<p>第一个例子是:</p>
<pre class="lang-py prettyprint-override"><code>p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))
print(to_str(p))
print(to_str(remove_elements(p, 6)))
</code></pre>
<pre class="lang-none prettyprint-override"><code>6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅
</code></pre>
<p>用你的另一个例子-</p>
<pre class="lang-py prettyprint-override"><code>q = node(1, node(1))
print(to_str(q))
print(to_str(remove_elements(q, 1)))
</code></pre>
<pre class="lang-none prettyprint-override"><code>1->1->∅
∅
</code></pre>
<p>下面是一个不可变(持久)单链表的实现-</p>
<pre class="lang-py prettyprint-override"><code>class node:
def __init__(self, head, next = None):
self.head = head
self.next = next
def remove_elements(t, val):
if not t:
return None
elif t.head == val:
return remove_elements(t.next, val)
else:
return node(t.head, remove_elements(t.next, val))
def to_str(t):
if not t:
return "∅"
else:
return str(t.head) + "->" + to_str(t.next)
</code></pre>
<p><strong>注意</strong></p>
<p>不可变实现不改变现有值。这意味着创造了新的价值观-</p>
<pre class="lang-py prettyprint-override"><code>p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))
q = remove_elements(p, 6)
</code></pre>
<p>当我们写入<code>q = remove_elements(p, 6)</code>时,将创建一个<em>新的</em>列表并将其存储到<code>q</code>,并且<code>p</code>保持不变-</p>
<pre class="lang-py prettyprint-override"><code>print(to_str(q))
print(to_str(p))
</code></pre>
<pre class="lang-none prettyprint-override"><code>1->2->3->4->5->∅ # q is a new list
6->1->2->6->3->4->5->6->∅ # p is unchanged
</code></pre>
<p><strong>解开</strong></p>
<p>注意<code>remove_elements</code>的每个实现都是一个普通函数,与类分离。如果您的程序需要基于类的解决方案,它将成为普通函数的简单包装器-</p>
<pre class="lang-py prettyprint-override"><code>class solution:
class remove_elements(self, t, val):
return remove_elements(t, val)
</code></pre>