如何在1秒内获取大型Linked List长度，解决遍历超时、递归栈溢出问题

• 你当前的迭代计数逻辑本身单次执行的耗时完全可以满足单次查询1秒内返回的要求，超时核心原因是测试用例中对size()方法执行了1000次重复调用：每次调用都需要从头遍历956142个节点，总遍历次数超过9.5亿次，自然会超出时间限制。
• 递归方案不可行的原因是95万+的链表深度远超过JVM默认的栈深度上限，必然触发栈溢出错误，没有优化空间。

采用空间换时间的思路，新增成员变量缓存链表长度，将size()查询复杂度从O(n)降到O(1)，修改步骤如下：

1. 首先在FilledBallots类中新增一个int类型的成员变量，用于缓存当前链表的长度：

private int size = 0;

2. 修改addVote()方法，每次成功添加节点后将缓存的长度加1：

public void addVote(String candidate, EmptyBallots ballots, Timestamp time) {       
    Ballot vote = ballots.remove();
    vote.fill(candidate, time);
    vote.next=null;
    if(head==null) {
        head=vote;
        tail=vote;
    }
    else {
        tail.next=vote;
        tail=vote;
    }
    // 新增长度更新逻辑
    size++;
}

3. 重写size()方法直接返回缓存的长度即可：

public int size() {
    return size;
}

修改后size()方法执行耗时为常数级，即使调用1000次总耗时也不会超过1ms，完全可以满足测试的时间要求，也不会出现栈溢出问题。如果后续补充了节点删除逻辑，只需在删除节点的代码中同步执行size--即可保证计数准确。

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