删除链表元素-递归问题

Question

我正在尝试解决"从具有值value "的整数链表中删除所有元素;问一个helper递归函数，但它不起作用。

Example:
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

我的解决方案:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def checkHead(self, head, val):
if head.val == val and head.next:
head = head.next
self.checkhead(head,val)
elif head.val and not head.next:
head = None

return head

def removeElements(self, head: ListNode, val: int) -> ListNode:
if not head:
return head

head = self.checkHead(head, val)

if not head:
return head

curr = head

while curr and curr.next:
if curr.next.val == val:
curr.next = curr.next.next

curr = curr.next
return None

失败的测试用例:

Input:  1->1, val = 1
Output: []

当我返回递归checkHead函数的值为head = self.checkHead(head, val)时，它表示head等于"1"但是当我调试它时，我可以看到程序从checkHead返回为None。我想知道问题出在哪里。

Answer 1

根本性缺陷

试图用迭代和变异来解决这个问题有一个根本性的缺陷。remove_elements可以调整head和next的属性，但是它不能将ListNode更改为None-

w = node(1)
print(w)      # ListNode { head = 1, next = None }
remove(w, 1)
print(w)      # ???

我们期望看到None作为结果，但这是不可能的，如果没有以下至少一个-

1. 函数调用必须更改
2. ListNode的数据结构必须更改

假设您想保持ListNode的形状，我们必须将函数调用调整为-

w = node(1)
print(w)
w = remove_elements(w, 1)   # <- reassign with result of call
print(w)

现在使用remove_elements的返回值，我们可以捕获ListNode降级为普通None的场景。使用第一个例子-

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))

6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅

第二个例子-

q = node(1, node(1))
print(to_str(q))
q = remove_elements(q, 1)    # <- reassign q
print(to_str(q))

1->1->∅
∅

下面是一个可变的实现单链表-

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 + "∅"

---

知道你的出身

这个问题被标记为recursion，这是正确的。链表是一种递归数据结构，选择递归程序来处理它可以使程序结构与数据结构相协调。然而，递归是函数式的遗产，因此将它与函数式风格结合使用会产生最好的结果。这意味着要避免诸如突变、变量重赋和其他副作用之类的事情。而不是销毁现有的值，创建一个新的值-

1. 如果输入列表t为空，则表示已达到基准情况。返回空列表
2. (感应)输入不为空;它至少有一个元素。如果第一个元素t.head与要删除的值val匹配，则返回子问题t.next
的结果
3. (感应)输入不为空，并且第一个元素不与要删除的值匹配。构造t.head的新列表节点和子问题t.next-
的结果

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

第一个例子-

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)))

6->1->2->6->3->4->5->6->∅
1->2->3->4->5->∅

使用你的其他例子-

q = node(1, node(1))
print(to_str(q))
print(to_str(remove_elements(q, 1)))

1->1->∅
∅

这是一个不可变(持久)单链表的实现-

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)

注意

不可变实现不会改变现有值。这意味着新值被创建-

p = node(6,node(1,node(2,node(6,node(3,node(4,node(5,node(6))))))))
q = remove_elements(p, 6)

写入q = remove_elements(p, 6)时，创建了一个新的列表并存储到q中，p保持不变-

print(to_str(q))
print(to_str(p))

1->2->3->4->5->∅                # q is a new list
6->1->2->6->3->4->5->6->∅       # p is unchanged

解开

注意remove_elements的每个实现都是一个普通函数，并且从类中分离出来。如果你的程序需要一个基于类的解决方案，它就变成了一个简单的包装器，包裹着我们的普通函数——

class solution:
class remove_elements(self, t, val):
return remove_elements(t, val)

Answer 2

如果您打算使用递归，您可以使用它来重新链接元素。这只需要removeElements函数本身递归:

def removeElements(self,head,val):
if not head: return None                           # end of list
if head.val == val:
head = self.removeElements(head.next,val)      # remove head
else:
head.next = self.removeElements(head.next,val) # keep head 
return head

Answer 3

代码中的问题如下:

• 当您递归地调用checkHead时，您不会捕获它返回的值，因此递归调用是无用的。它唯一的用处是返回。因此，就像在removeElements中已经正确地做的那样，您也应该在这里将返回值赋给head:

  head = self.checkhead(head,val)
  

• elif head.val错误。应该是elif head.val == val。很遗憾你需要这个elif。如果让if条件(在它上面)测试head而不是head.next，则根本不需要elif情况。

• while curr循环不能很好地处理搜索值在一行中出现两次的情况。在这种情况下，您还将cur移动到cur.next，下一次迭代将不再查看cur.val，而是查看cur.next.val。所以cur的值永远不会被检查。所以…你应该在else块中做cur = cur.next。

• 最终return是错误的。您不应该返回None，因为while cur循环可能在列表中保留了一些节点。所以返回head

有了这些变化，也就不需要有两个if not head检查了:现在都可以省略了。

下面是更正后的代码:

class Solution:
def checkHead(self, head, val):
# Check that head is not None, instead of checking head.next
if head and head.val == val:
# Should use the value returned by recursive call
head = self.checkHead(head.next, val)
return head
def removeElements(self, head: ListNode, val: int) -> ListNode:
head = self.checkHead(head, val)
curr = head 
while curr and curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else: # Only move to next when no match
curr = curr.next
return head  # Should return head, not None

这将工作。尽管如此，看到递归和迭代代码的混合还是有点奇怪，这也是除了removeElements之外还需要一个单独方法的原因。实际上你可以用递归做所有的事情:

class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if head:
if head.val == val:
return self.removeElements(head.next, val)
else:
head.next = self.removeElements(head.next, val)
return head