如何创建一个递归函数从链表中删除节点与给定的关键字在python?

Question

我尝试程序从链表中递归删除节点。我的程序如下

class node:
def __init__(self, data=None):
self.data = data
self.next = None
class linkedList:
def __init__(self):
self.head=None
def printList(self):
cur = self.head
while(cur != None):
print(cur.data,end="->")
cur=cur.next
print("null")
def push(self,dat):
newNode = node(dat)
temp = self.head
self.head = newNode
newNode.next = temp
@staticmethod
def dnr(head, key):
if head is not None:
if head.data == key:
head=head.next
return head
if head is not None:
head.next = linkedList.dnr(head.next, key)
return head
return head


if __name__ == '__main__':
ll=linkedList()
ll.push(3)
ll.push(6)
ll.push(9)
ll.push(12)
ll.push(15)
ll.printList()
print("*******")
# ll.head = linkedList.dnr(ll.head,2)
linkedList.dnr(ll.head,9)
ll.printList()

的问题是，这对第一个元素不起作用。为了使它对第一个元素起作用，我必须像这样调用函数ll.head = linkedList.dnr(ll.head,2)

第二件事是我希望我的函数以这种方式调用ll.dnr(2)

请告诉我如何在python中创建一个递归函数来删除链表中的节点

Answer 1

我重写了你的代码:

class node:
def __init__(self, data=None):
self.data = data
self.next = None
class linkedList:
def __init__(self):
self.__head=None
def printList(self):
cur = self.__head
while(cur != None):
print(cur.data,end="->")
cur=cur.next
print("null")
def push(self,dat):
newNode = node(dat)
temp = self.__head
self.__head = newNode
newNode.next = temp

@staticmethod
def __dnr(head, key):
if head is None: 
return head
if head.data == key:
head = head.next
return head
head.next = linkedList.__dnr(head.next, key)
return head

@staticmethod
def dnr(listObj, key):
if listObj is None or listObj.__head is None: 
return listObj
if listObj.__head.data == key:
listObj.__head = listObj.__head
listObj.__head = linkedList.__dnr(listObj.__head, key)
def deleteKey(self, key):
linkedList.dnr(self, key)
if __name__ == '__main__':
ll=linkedList()
ll.push(3)
ll.push(6)
ll.push(9)
ll.push(12)
ll.push(15)
ll.printList()
print("*******")
linkedList.dnr(ll, 9)
ll.deleteKey(12)
ll.printList()

我在linkedList类内部设置了head变量私有，让类核心组件访问外部世界是不明智的。类核心组件永远不应该泄漏给外部世界，因为如果使用不当，可能会导致错误。所以我重写了你的dnr函数，现在它更清楚了，它不返回head对象，这是linkedList类的核心组件。现在dnr函数只是检查传递的listObj是否有效，并检查head是否是应该删除的节点。之后，它调用私有静态__dnr函数来删除给定key的节点。函数deleteKey可以像这样调用ll.deleteKey(12)，这就是你想要的。

让核心组件可以通过外部世界访问，就像让银行客户可以访问银行金库一样。不是每个人都会试着从里面偷钱，但总有人会试着去偷。

如果你不明白私有变量的含义，请遵循此链接。

Answer 2

我希望我的函数这样调用ll.dnr(2)

然后你需要定义一个instance方法。您的静态函数可以达到目的，但是正如您注意到的，您确实需要将其返回值赋给列表的head属性，以确保它在删除原始头节点时也能工作。对于静态方法，您无法避免这种开销，因为该方法不了解您的linkedList实例。

您可以通过添加instance方法来实现您想要的，该方法将依赖于现有的静态方法，并将此赋值处理回实例的head属性。

将此添加到您的linkedList类:

def remove(self, key):
self.head = linkedList.dnr(self.head, key)

现在在你的主程序中你可以这样做:

ll.remove(15)

旁注:您不需要在静态方法中进行第二次if head is not None:检查，因为当执行到代码中的该点时，此条件将始终为真。只要无条件地赋值给head.next。

附录

如果您希望dnr本身成为实例方法(不添加remove方法)，那么您需要暂时从列表中切断头节点(即使您想保留它)，循环，然后有条件地再次添加该切断节点(如果它的键不是要删除的键)。

它看起来像这样:

def dnr(self, key):
head = self.head
if head:
self.head = head.next # Skip
if head.data != key: # Need to restore it
self.dnr(key) # But first look further...
head.next = self.head # Prefix the removed node
self.head = head  # ...and make it the head again

你可以这样调用:

ll.dnr(15)