使用递归查找链表长度的Python程序

当需要使用递归查找链表长度时，定义一种方法来向链表添加元素，并定义一种方法来计算链表的长度。定义了一个帮助函数，通过先前定义的长度计算方法来调用它。

以下是示例−

示例

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

class my_linked_list:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_value(self, my_data):
        if self.last_node is None:
            self.head = Node(my_data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(my_data)
            self.last_node = self.last_node.next

    def calculate_length(self):
        return self.length_helper_fun(self.head)

    def length_helper_fun(self, curr):
        if curr is None:
            return 0
        return 1 + self.length_helper_fun(curr.next)

my_instance = my_linked_list()
my_data = input('Enter elements of the linked list ').split()
for elem in my_data:
    my_instance.add_value(int(elem))
print('The length of the linked list is ' + str(my_instance.calculate_length()))

输出

Enter elements of the linked list 12 45 32 67 88 0 99
The length of the linked list is 7

解释

• 创建了’Node’类。

• 创建了另一个具有所需属性的’my_linked_list’类。

• 它具有一个初始化函数，用于将第一个元素即’head’初始化为’None’，最后一个节点初始化为’None’。

• 定义了另一个名为’add_value’的方法，用于向链表中添加数据。

• 定义了另一个名为’calculate_length’的方法，用于调用帮助函数以查找链表的长度。

• 定义了帮助函数，因为需要在此处使用递归。

• 它检查节点的当前值，并返回列表的长度。

• 创建了’my_linked_list’类的一个对象。

• 获取用户输入的链表元素。

• 对其调用方法以添加数据。

• 调用calculate_length方法，并在控制台上显示输出。