链表重复元素计数代码边界测试用例失败原因排查

你的代码在小规模样例下能跑出正确结果，但碰到边界和大规模用例时会失败，核心问题有两个：

• 时间复杂度严重不满足约束。题目明确说明节点总数N最高可达1e5，你采用的双重循环暴力比对逻辑时间复杂度为O(n²)，当N=1e5时总运算量达到10^{10次，远超出常规判题环境1秒内可承载的10}8次运算上限，会直接触发超时，根本无法跑完大规模测试用例。
• 存在空指针崩溃的边界漏洞。循环的入口判断是while(head.next != null)，如果输入是空链表（对应N=0的边界场景，传入的head本身为null），执行判断时直接访问null的next属性，会抛出NullPointerException导致程序直接崩溃，无法处理空输入场景。

把暴力比对的逻辑改成单次遍历+已出现值标记，把时间复杂度降到O(n)即可：

1. 首先做边界判断：如果传入的head为null，直接返回0，避免空指针
2. 初始化标记结构用来存已经遍历过的节点值（因为节点值最高为1e6，用长度1e6+1的布尔数组做标记速度比哈希集合更快），初始化重复计数器为0
3. 从链表头开始逐节点遍历：
   • 如果当前节点值已经在标记结构中，说明是重复元素，计数器加1
   • 如果当前节点值不在标记结构中，把值加入标记
   • 指针移动到下一个节点，直到遍历完整个链表
4. 最终返回计数器的值即可

对应实现代码参考：

import crio.ds.List.*;

/*public class ListNode {
   public int val;
   public ListNode next;
   public ListNode(int x) { val = x; next = null; }
}*/

public class Solution {
    public int countDuplicatesInALinkedList(ListNode head){
        if (head == null) {
            return 0;
        }
        int counter = 0;
        // 节点值最大为1e6，用数组标记比哈希集性能更高
        boolean[] seen = new boolean[1000001];
        seen[head.val] = true;
        head = head.next;
        while (head != null) {
            if (seen[head.val]) {
                counter++;
            } else {
                seen[head.val] = true;
            }
            head = head.next;
        }
        return counter;
    }
}

以上实现单次遍历即可完成统计，时间复杂度O(n)，可以轻松扛住1e5规模的输入，同时覆盖了空链表的边界场景，和样例的计算逻辑完全匹配：对输入1 2 3 4 4 5 6 6 6统计时，第二个4、第二个6、第三个6会被判定为重复元素，最终返回结果3，和样例输出一致。

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