链表中出现次数最多的字符

什么是链表？

在计算机科学中，链表（Linked list）是一种常见的数据结构，是一种线性表，但是不像顺序表那样在物理上连续存储数据，而是通过链表中的指针进行连接。链表可以充分利用计算机内存空间，实现灵活的内存动态管理。

字符统计问题的背景

在一些编程题中，经常会遇到需要统计链表中出现次数最多的字符的问题。例如：

问题描述：给定一个链表，其节点的值为单个字符。请编写一个函数，返回这个链表中出现次数最多的字符的 ASCII 值。

有了这个问题，我们就可以尝试寻找解决方案。

解决方案的思路

暴力枚举

最暴力的方法是，枚举每个字符并计算出现次数，然后找到出现次数最多的字符。这个方法的时间复杂度为O(n2)，其中n是链表中节点的数量。

//暴力枚举解法

char mostFrequentChar(Node* head) {
    int maxCnt = 0;
    char res;
    Node* p = head;
    while (p != nullptr) {
        int cnt = 0;
        char cur = p -> val;
        Node* q = p;
        while (q != nullptr) {
            if (q -> val == cur) {
                cnt++;
            }
            q = q -> next;
        }
        if (cnt > maxCnt) {
            maxCnt = cnt;
            res = cur;
        }
        p = p -> next;
    }
    return res;    
}

这个算法的时间复杂度很高，因此需要寻找更为高效的算法。

哈希表

哈希表可以实现常数时间内的插入和访问操作，因此可以用哈希表实现出现次数的统计。具体地，遍历链表，将每个字符出现次数记录在哈希表中，最后找到哈希表中出现次数最多的字符。这个算法的时间复杂度为O(n)。

//哈希表解法

char mostFrequentChar(Node* head) {
    int hash[256] = {0};
    Node* p = head;
    while (p != nullptr) {
        hash[p -> val]++;
        p = p -> next;
    }
    int maxCnt = 0;
    char res;
    for (int i = 0; i < 256; i++) {
        if (hash[i] > maxCnt) {
            maxCnt = hash[i];
            res = i;
        }
    }
    return res;
}

桶排序

哈希表的优点是简单易懂，但是需要额外的空间来存储哈希表。如果不想使用额外空间，可以考虑使用桶排序。具体地，用一个长度为256的桶来实现出现次数的统计，最后找到出现次数最多的字符。这个算法的时间复杂度也为O(n)。

//桶排序解法

char mostFrequentChar(Node* head) {
    int count[256] = {0};
    Node* p = head;
    while (p != nullptr) {
        count[p -> val]++;
        p = p -> next;
    }
    int maxCnt = 0;
    char res;
    for (int i = 0; i < 256; i++) {
        if (count[i] > maxCnt) {
            maxCnt = count[i];
            res = i;
        }
    }
    return res;
}

小结

链表中出现次数最多的字符是一道经典的编程题，可以应用到各种场景中。本文介绍了三种解决方案，分别是暴力枚举、哈希表和桶排序。其中，哈希表和桶排序都能够在时间复杂度上做到O(n)，是更为高效的解决方案。如果不想使用额外空间，则应该采用桶排序。