时间戳

首页 > 解决方案 > 如何递归地添加到 Python 中的链表？

python - 如何递归地添加到 Python 中的链表？

问题描述

我在使用带有链表的递归时遇到了麻烦。我希望能够将另一个节点添加到有序链表中。

我有这堂课：

class Link:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

下面是递归函数，到目前为止除了识别基本情况外，它并没有做太多事情

注意：它不是一个方法Link，它是一个单独的函数：

def add(ll, v):
    if ll == None:
        return Link(v)
    else:
         ll.next = add(ll.next,v)
         return ll

示例：我有这个链表A：

1->3->8->12->None

我调用add(A, 10)which 应该以正确的顺序添加 10。

1->3->8->10->12->None

我应该如何修改我的代码以使其正常工作？

标签： pythonrecursionlinked-list

解决方案

您需要一个额外的基本情况，当您找到一个不小于您要按顺序插入的值时停止递归：

elif v <= ll.value:
    return Link(v, ll)

所以完整的代码可能是：

class Link:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

    def values(self):
        yield self.value
        if self.next:
            yield from self.next.values()

def add(ll, v):
    if ll is None:
        return Link(v)
    elif v <= ll.value:
        return Link(v, ll)
    else:
        ll.next = add(ll.next, v)
        return ll

# example list
A = Link(1, Link(3, Link(8, Link(12))))
# add 10 to it:
A = add(A, 10)
# print list
print(list(A.values()))

推荐阅读