想起一道面试题

突然想起，前段时间到某互联网公司面试的时候一道题。当时没想到任何方案，现在有点堵得慌，在这里求解。

题目
不用任何临时变量，求单链表的长度。

================
补充：题目是面试官口述的，是他临时想到的一个题目。所以表述的可能没那么严谨，也可能是我记得不全。大家就按代码中没有临时变量来理解吧。至于机器实现，肯定会有临时存储，大家不必太较真。

什么样算临时变量？函数的参数算不算？

只有链表头指针这一个参数

int lll(node* p) {
    if (!p->next)
        return 1;
    return 1 + lll(p->next);
}

这算不用临时变量吗？

佩服，昨天晚上看SICP第一章，里面总是在“迭代”和“递归”之间转换和比较，我若有所获。
看到这道题目，我思路限制在“迭代”里面，总是想着遍历链表，于是答不上来。

看了你的回复豁然开朗，除了迭代，我们要多想想递归。


PS后补：但是这道题的说不用临时变量，本质是减少资源消耗。但是递归的代价比迭代要高的多啊。

迭代 时间$(n)+空间$(1)
递归 时间$(n)+空间$(n)

可见递归更占资源，为了少一个临时变量而增加重复的堆栈保持迭代副本，其实得不偿失啊。

用递归试一试

我是感觉这种方式用的临时变量就更多了。
不是表面中没有int number就是没有使用临时变量的。

如果把题目改成，如果不声明int number的方式，如何得到单链表的长度。
如果在Java中，调用函数的时候，就会把this和函数的参数放入栈的变量列表中。这些也算是临时变量的一种的。
理论上来说，使用int number的速度(迭代)怎么也比递归快了。
只要判断p->next是不为空，就可以对number不断的加1，直到null为止。

一般都是要多想想能不能迭代，而不是想想能不能递归吧。递归写出来的程序都是比较接近数学的公式，更容易被人所理解的。

如果是你，怎么解答这道题目呢？

佩服，我第一眼想到了是递归，但还是没写出来。基础还是太薄了。
谢谢！

我的概念里面就没有不需要临时变量就能得到链表长度的程序。
链表的长度难道不是临时变量？难道是链表自身就带有的变量？都是临时创建出来，然后赋值的。
当然你可以说面试官要的是代码里面没有临时变量。
那么如果用动态语言，直接提供返回单链表的长度，那还要什么临时变量，直接就是linkedList.length()就可以啦。
所以这个面试题。。。我不会。

然后面试官就会觉得，你连递归都不会啊。然后我就无语，说没有临时变量真的不会，然后我就离开面试现场。