递归统计链表节点数原理及常数1与指针相加逻辑疑问

int length(Node *head) {
  if(head == nullptr)
    return 0;

  return 1 + length(head->link);
}

链表节点数量统计的实现逻辑 #

这个函数采用递归的拆解思路，把整个链表的长度拆为「当前节点」+「当前节点之后的子链表长度」两部分计算：

• 终止条件：当传入的指针head是空指针nullptr时，说明已经遍历到链表末尾，没有节点需要计数，直接返回0
• 递归逻辑：只要当前head不为空，就代表这是一个有效节点，先计1个数，再计算当前节点的下一个节点head->link作为头的子链表长度，两个值相加就是当前链表的总长度

举个实际的调用例子，假设链表为A→B→C→null，总长度为3：

• 传入节点A调用函数，返回1 + length(B)
• 传入节点B调用函数，返回1 + length(C)
• 传入节点C调用函数，返回1 + length(nullptr)
• 传入null调用函数返回0
• 逐层回代计算得到1+1+1+0=3，就是最终的链表长度

关于“常数1和指针地址相加”的误解 #

这里不存在整数和指针地址相加的操作，属于对返回逻辑的误解：
return 1 + length(head->link)里的head->link确实是指针，但它只是调用length函数的入参，length函数的返回值是int类型的整数，也就是子链表的长度，所以实际执行的是两个整数相加，完全符合语法规则。

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