删除链表元素递归问题

Question

我试图用一个辅助递归函数来解决“从一个有值val的整数链表中删除所有元素”的问题，但它不起作用

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

如果要使用递归，可以使用它在运行时重新链接元素。这只需要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 2

以下是代码中的问题：

• 当您递归调用checkHead时，不会捕获它返回的值，因此递归调用是无用的。它唯一的实用程序是它返回的内容。因此，正如您在removeElements中已经正确执行的操作一样，您还应该在此处将返回值分配给head：

  head = self.checkhead(head,val)
  

• elif head.val是错误的。它应该是elif head.val == val。很遗憾你根本就需要这个。如果您将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

Answer 3

基本缺陷

试图通过迭代和变异来解决这个问题有一个基本缺陷。尽可能努力，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)