如何基于循环链表实现列表重复元素的数量统计功能

现有代码问题 #

你提交的代码中prev和temp两个指针始终同步移动，指向同一个节点，因此相等判断永远成立，最终统计结果就是链表的总节点数，没有实现重复项统计逻辑。

修复实现 #

推荐优先使用哈希表统计频次的方案，时间复杂度为O(n)，实现简单不易出错：

import java.util.HashMap;
import java.util.Map;

public int countDuplicateElements() {
    // 统计每个元素的出现频次
    Map<E, Integer> freqMap = new HashMap<>();
    if (isEmpty()) {
        return 0;
    }
    Node<E> temp = current;
    do {
        freqMap.put(temp.element, freqMap.getOrDefault(temp.element, 0) + 1);
        temp = temp.next;
    } while (temp != current);
    
    // 统计出现次数超过1次的元素个数
    int duplicateCount = 0;
    for (int freq : freqMap.values()) {
        if (freq > 1) {
            duplicateCount++;
        }
    }
    return duplicateCount;
}

如果要求不能使用额外的集合存储，可使用双重遍历的低空间复杂度方案，适合小数据量场景：

public int countDuplicateElements() {
    if (isEmpty()) {
        return 0;
    }
    int duplicateCount = 0;
    Node<E> outer = current;
    // 外层遍历每个元素
    do {
        // 先统计当前元素的出现次数
        int currentFreq = 0;
        Node<E> inner = current;
        do {
            // 注意用equals比较值相等，避免引用类型判断错误
            if (inner.element.equals(outer.element)) {
                currentFreq++;
            }
            inner = inner.next;
        } while (inner != current);
        
        // 出现次数>1时，仅第一次遇到该元素时计数，避免重复统计
        if (currentFreq > 1) {
            Node<E> check = current;
            boolean alreadyCounted = false;
            while (check != outer) {
                if (check.element.equals(outer.element)) {
                    alreadyCounted = true;
                    break;
                }
                check = check.next;
            }
            if (!alreadyCounted) {
                duplicateCount++;
            }
        }
        outer = outer.next;
    } while (outer != current);
    
    return duplicateCount;
}

注意事项 #

• 两种方案均兼容你给出的测试用例，输入[30, 30, 50, 50, 80, 90, 10, 10]时返回正确结果3
• 判断元素相等时使用equals而非==，避免引用类型元素的相等判断逻辑错误，如果是自定义元素类型需确保已经重写equals方法

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