Python中基于递归实现链表长度计算的问题求助

嘿，作为Python新手能写出完整的链表类已经超棒啦！我看到你卡在了用递归计算链表长度这一步，咱们来把这个问题拆解清楚，一步步解决它。

先理清楚递归的核心逻辑 #

递归计算链表长度的思路其实很简单，核心就两点：

• 终止条件：当当前节点是None（也就是走到链表末尾了），返回0——因为这里没有节点可以计数了。
• 递归步骤：如果当前节点存在，那长度就是1（当前这个节点）加上下一个节点开始的链表长度，也就是递归调用函数处理当前节点的next。

你的现有代码问题 #

看了你写的node_number方法，这里有几个明显的问题：

• 把节点引用转成字符串做正则匹配完全没必要，函数的输入应该是节点对象，不是字符串；
• 没有正确的终止条件，递归会无限循环直到报错；
• 递归调用时没有传递下一个节点的参数，return self.node_number这种写法是错误的；
• 你用了count +=1的迭代思路，和递归的逻辑不符。

正确的实现方式 #

我们可以写一个独立的递归函数，或者修改你链表类里的方法，两种方式都可以：

方式1：独立的递归函数

这个函数直接接收节点引用作为参数，非常直观：

def calculate_linked_list_length(current_node):
    # 终止条件：到达链表末尾，返回0
    if current_node is None:
        return 0
    # 递归：当前节点算1，加上下一个节点开始的链表长度
    return 1 + calculate_linked_list_length(current_node.next)

使用的时候，直接传入链表的头节点就行：

# 创建链表并添加元素
my_list = linked_list()
my_list.add_first("A")
my_list.add_first("B")
my_list.add_last("C")

# 计算长度
print(calculate_linked_list_length(my_list.head))  # 输出：3

方式2：作为链表类的方法

如果你想把这个功能整合到linked_list类里，可以修改node_number方法：

class linked_list:
    # （保留你原来的所有方法）
    
    def node_number(self, current_node):
        # 终止条件：没有节点了，返回0
        if current_node is None:
            return 0
        # 递归调用，处理下一个节点
        return 1 + self.node_number(current_node.get_next_node())

调用的时候这样用：

my_list = linked_list()
my_list.add_last(1)
my_list.add_last(2)
my_list.add_last(3)

print(my_list.node_number(my_list.head))  # 输出：3

再解释下递归的执行过程 #

比如链表是B -> A -> C -> None，递归的执行流程是这样的：

1. 调用calculate_linked_list_length(B)，返回1 + calculate_linked_list_length(A)
2. 调用calculate_linked_list_length(A)，返回1 + calculate_linked_list_length(C)
3. 调用calculate_linked_list_length(C)，返回1 + calculate_linked_list_length(None)
4. 调用calculate_linked_list_length(None)，返回0
5. 然后从底层往上加：1+0=1，1+1=2，1+2=3，最终得到总长度3

这样是不是就清晰多啦？

内容的提问来源于stack exchange，提问作者Horizoner 2.0