python - 使用递归从链表中删除一个值

Question

我的任务是从链表中删除第一个出现的值。该值由用户输入。然后，我还必须返回一个布尔值，指示该项目是否已被删除 (True)，或者如果该值不在链表中，则返回 False。这就是我到目前为止所拥有的。

def remove(lst, value):
    lst.head = removeRec(lst.head, value)

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        print("Cannot remove value from an empty list")
    elif node.data == value:
        return node.next
    elif:
        node.next = removeRec(node.next, value)
        return node
    else:
        return False

这样做的问题是，如果项目被删除，它不会返回 True。我将如何实施？另外，我将如何迭代地实现类似的功能。多谢你们。

Answer 1

报告您未能实现您被要求做的事情的“Pythonic”方式是引发异常。这使您的代码相当简单：

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        raise ValueError("Cannot remove value from an empty list")
    elif node.data == value:
        return node.next
    else:
        node.next = removeRec(node.next, value)
        return node

这将适用于您现有的remove函数，将其留给调用者来处理调用代码中的异常。但是，如果您希望remove函数返回一个指示成功或失败的布尔值，您可以在此处捕获异常：

def remove(lst, value):
    try:
        lst.head = removeRec(lst.head, value)
        return True # only reached if no exception was raised by the recursion
    except ValueError:
        return False

如果出于某种原因（例如在尚未教授它们的课程中）您坚决反对使用异常，您可以在递归调用的返回值中编码删除失败，但是您需要对其进行额外检查，以避免损坏您的列表：

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        print("Cannot remove value from an empty list")
        return None    # your code did this implicitly, I'm being explicit
    elif node.data == value:
        return node.next
    else:
        rec_result = removeRec(node.next, value)
        if rec_result is None:
            return rec_result
        else:
            node.next = rec_result
            return node

然后，您可以对非递归函数中的递归情况进行相同的检查，并将结果值转换为布尔值：

def remove(lst, value):
    rec_result = removeRec(lst.head, value)
    if rec_result is None:
        return False
    else:
        lst.head = rec_result
        return True

Answer 2

您需要从基本案例开始

1. 该值位于列表的开头
2. 该值位于列表的末尾
3. 该值在列表的中间
4. 该值不在列表中

现在由于大多数列表的性质，您可以将最终值视为与列表中间相同

所以我们真的有

1. 该值位于列表的开头
2. 该值不在列表中
3. 所有其他情况

作为我们的基本案例，既然您了解了基本案例，您就可以编写函数了

def removeRec(node,value):
   if node.value == value: #only time this will happen is if the node is at the head
      node.value = node.next.value
      node.next = node.next.next
      #you cannot simply say node= node.next since then it will not propagate to the actual list
      return True # found and removed value
   if node.next == None: #case where value is not in the list
      return False #unable to remove
   if node.next.value == value:
       node.next = node.next.next 
       return True #successfully removed
   return removeRec(node.next,value)#recursively continue searching

由于节点是可变对象，因此列表只会被更新......它不会返回新列表

Answer 3

我会这样做：

def remove(lst, value):
    remove.ret = False

    def removeRec(node, value):
        if isinstance(node, EmptyNode):
            print("Cannot remove value from an empty list")
        elif node.data == value:
            remove.ret = True
            return node.next
        else:
            node.next = removeRec(node.next, value)
            return node

    lst.head = removeRec(lst.head, value)
    return remove.ret

Answer 4

如果链表中有重复项

def removeLinkedList(node, value):
    if not node:
        return node
    elif node.val == value:
        return removeLinkedList(node.next,value)
    else:
        node.next = removeLinkedList(node.next, value)
        return node