如何实现O(1)空间、不修改原结构的IntList迭代求长纯函数

完全可以在满足要求的前提下实现该方法，核心思路是避免修改原链表的成员指针，仅用临时指针遍历即可。

正确代码实现 #

public int getSizeIterative() {
    int size = 0;
    // 声明临时指针指向当前节点，全程不修改原对象的任何属性
    IntList current = this;
    while (current != null) {
        size++;
        // 仅移动临时指针，原链表的rest指针不会发生任何变化
        current = current.rest;
    }
    return size;
}

方案特性说明 #

• 空间复杂度严格为O(1)：仅额外使用了两个固定大小的变量（int类型的size和引用类型的current），没有拷贝任何链表节点，也没有申请和链表长度正相关的内存空间。
• 属于纯函数实现：全程没有修改原链表的任何成员变量，无论调用多少次都会返回一致的正确结果，不会破坏原链表的结构。

原有实现问题分析 #

1. 最初的错误迭代版本直接修改了this.rest，相当于执行过程中直接截断了原链表的后续节点，因此第二次调用时原链表的rest已经被置为null，返回错误结果1。
2. 后续的拷贝节点版本虽然解决了原链表被修改的问题，但属于不必要的额外开销，完全可以通过临时遍历指针规避。

补充说明：你提供的原递归方法存在笔误，方法内调用的rest.getSizeRecur()和实际声明的方法名getSizeRecursive()不一致，实际运行会抛出方法未找到异常，修改为同名即可正常运行。

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