python - 为 Linked-List 类实现递归 Add 方法时遇到问题

Question

我需要递归地实现链表类的add方法。我无法让我的代码工作。这是我到目前为止所拥有的:

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, val, current_node=0):

        if current_node == 0:
            current_node = self.head

        if current_node is None:
            current_node = Node(val)
        else:
            self.add(self, val, current_node.next)

我的这个实现哪里出了问题？

Answer 1

这是对递归的滥用。如果链表的长度大于调用堆栈的大小，则类会无缘无故地中断。与迭代实现相比，它的编写效率也较低且不太直观。

话虽如此，教授们通常会要求那些天生不适合递归的算法以递归方式实现。一起玩，我会编写一个内部助手来处理实际的递归。这避免了尴尬的默认参数，它可能会让调用者感到困惑，并使他们破坏函数的契约。

def add(self, val):
    def add_recursively(curr, prev):
        if curr:
            add_recursively(curr.next, curr)
        else:
            if prev:
                prev.next = Node(val)
            else:
                self.head = Node(val)

    add_recursively(self.head, None)

最初尝试的主要问题是:

if current_node is None:
    current_node = Node(val)

如果没有对链中前一个节点的引用，current_node 实际上不会使用上述操作附加到任何内容，因此它只是在函数返回时被垃圾收集。

如果允许使用迭代，这是一种更自然的方法:

def add(self, val):
    curr = self.head
    prev = None

    while curr:
        prev, curr = curr, curr.next

    if prev:
        prev.next = Node(val)
    else:
        self.head = Node(val)

这是一个最小的、完整的使用示例:

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

    def __str__(self): 
        return str(self.val)

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, val):
        curr = self.head
        prev = None

        while curr:
            prev, curr = curr, curr.next

        if prev:
            prev.next = Node(val)
        else:
            self.head = Node(val)

    def __str__(self): 
        nodes = []
        curr = self.head

        while curr:
            nodes.append(curr.val)
            curr = curr.next

        return "[" + " -> ".join(nodes) + "]"

if __name__ == "__main__":
    llist = LinkedList()
    llist.add("bananas")
    llist.add("apples")
    llist.add("cranberries")
    print(llist) # => [bananas -> apples -> cranberries]

除此之外，请考虑为您的 LinkedList 类保留一个 self.tail 节点引用。这将使加法操作复杂度为 O(1)，而不是 O(n)。