链表递归删除操作：如何换头？

Question

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def rec_delete(head, val, prev=None):
    if(head == None):
        return False
    if(head.val == val):
        if(prev == None):
            head = head.next
        else:
            prev.next = head.next
        return True
    
    return rec_delete(head.next, val, head)


head = Node(1, Node(2, Node(3, Node(4))))
rec_delete(head, 1)
rec_delete(head, 2)
rec_delete(head, 3)
rec_delete(head, 4)

给定一个链表 1 -> 2 -> 3 -> 4 我想一个一个地删除所有元素，但不确定如何在 python 中分配一个新的头。我当前代码的问题是因为 head 通过了一个我无法重新分配 head 的函数。我希望 head 在所有操作后成为 None。

Answer 1

您的 delete 函数需要 return 删除 val 之后列表的 head。这不仅使删除的实现更加简单（基本情况是头部本身被删除的情况），调用者必须能够处理头部被删除的情况。

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
        
    def __repr__(self):
        """val1 -> val2 -> val3 ..."""
        return f"{self.val}" + (f" -> {self.next}" if self.next else "")


def delete(head, val):
    """Delete val from list with given head, returning head of the modified list."""
    if head.val == val:
        # Deleting head, so the new head is head.next.
        return head.next
    # Head remains head, but we still need to delete val from head.next.
    head.next = delete(head.next, val)
    return head


head = Node(1, Node(2, Node(3, Node(4))))
print(head)  # 1 -> 2 -> 3 -> 4
head = delete(head, 1)
head = delete(head, 2)
print(head)  # 3 -> 4
head = delete(head, 3)
head = delete(head, 4)
print(head)  # None

链表递归删除操作：如何换头？

Linked list recursive delete operation: How do I change the head?

python

linked-list