java单链表计数算法

Question

我需要写一个metod，它遍历一个排序的单链表并返回 出现次数最多但仅在列表中出现一次的数字

有人能给我指出正确的方向吗

还找不到elegent解决方案，我应该使用递归吗

我希望代码尽可能高效

提前谢谢

Answer 1

 public int findMoreRecurrentValue(List<Integer> sortedList) {
    if(sortedList.size() == 0) return -1;
    int mostRecurrent = -1;
    int nReccurrences = 0;
    int n = 1;
    int current = sortedList.get(0);
    for(int i = 1; i < sortedList.size(); ++i) {
        if(sortedList.get(i) == current)
            ++n;
        else {
            if(n > nReccurrences) { 
                mostRecurrent = current;
                nReccurrences = n;
            }
            current = sortedList.get(i);
            n = 1;
        }
    }
    // Check again at the end, the most reccurrent value could be the last one.
    if(n > nReccurrences) {
        mostRecurrent = current;
        nReccurrences = n;
    }

    return mostRecurrent;
}

Answer 2

你可以使用HashMap<index,count> 遍历链表 如果你发现相同的数字，那么增加计数 最后检查哪个计数是大的，并返回其索引