使用递归从链表中删除值

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