链表去重优化：求删除出现次数≥x的元素的高效算法

问题背景 #

需要实现一个函数，输入单链表头节点和最大允许出现次数x，删除链表中所有出现次数≥x的元素。当前实现通过反复调用find和delete函数完成，但计算效率低下；同时由于元素值可能是大数，无法通过创建数值范围对应的数组来统计出现次数，因此需要更高效的算法。

当前实现代码 #

typedef struct n_s
{
    int val;
    struct n_s *next;
}
n_t;

// 删除链表h中所有值为del的节点
n_t * delete(n_t *h, int del);
// 在链表h中查找第一个值为find的节点，不存在则返回NULL
n_t * find(n_t *h, int find);

n_t *
delFromList(n_t *h, int x)
{
    int val;
    n_t *el, *posInter;

    // 空链表处理
    if (h == NULL)
        return NULL;

    // 处理头节点
    val=h->val;
    if ( (posInter = find(h -> next,val)) 
        && (find(posInter -> next, val)))
        h = delete(h, val);

    // 从第二个节点开始遍历
    el = h;
    while (el -> next)
    {
        val = el -> next -> val;
        // 检查是否需要删除下一个节点，删除后重新检查新的下一个节点
        if ((posInter = find(el -> next -> next, val))                   
            && (find(posInter -> next, val)))
            el -> next = delete(el -> next, val);
        // 未删除节点则向后移动
        else 
            el = el -> next;

    }

    return h;
}

注：代码中el->next->next的写法虽显复杂，但作者认为比使用额外变量（如next、past）更直观。

现有实现的效率瓶颈 #

当前方案的核心问题是重复遍历链表：

• 每次调用find都会从头（或当前节点后）遍历查找目标值，时间复杂度为O(n)；
• 对每个节点多次调用find判断出现次数，再调用delete再次遍历删除对应节点，整体时间复杂度达到O(n²)，链表较长时性能会急剧下降。

优化方案：两次遍历+哈希表统计 #

核心思路 #

1. 第一次遍历：统计频次
   用哈希表（不受元素数值大小限制）遍历链表一次，记录每个val的出现次数。这一步时间复杂度O(n)，空间复杂度O(k)（k为链表中不同值的数量，远小于n）。
2. 第二次遍历：删除节点
   再次遍历链表，查询哈希表中对应值的频次，若≥x则删除该节点。用哑节点简化头节点删除逻辑，维护前驱节点避免重复查找，这一步时间复杂度O(n)。

示例实现 #

#include <stdlib.h>
#include <limits.h>

// 哈希表节点结构
typedef struct hash_node_s {
    int key;
    int count;
    struct hash_node_s *next;
} hash_node_t;

// 哈希表结构
typedef struct hash_s {
    int size;
    hash_node_t **buckets;
} hash_t;

// 创建哈希表
static hash_t* hash_create(int size) {
    hash_t *hash = malloc(sizeof(hash_t));
    hash->size = size;
    hash->buckets = calloc(size, sizeof(hash_node_t*));
    return hash;
}

// 哈希函数（取模实现，可按需优化）
static int hash_func(int key, int size) {
    return abs(key) % size;
}

// 更新哈希表中对应key的计数
static void hash_update_count(hash_t *hash, int key) {
    int idx = hash_func(key, hash->size);
    hash_node_t *node = hash->buckets[idx];
    while (node) {
        if (node->key == key) {
            node->count++;
            return;
        }
        node = node->next;
    }
    // 不存在则新增节点
    hash_node_t *new_node = malloc(sizeof(hash_node_t));
    new_node->key = key;
    new_node->count = 1;
    new_node->next = hash->buckets[idx];
    hash->buckets[idx] = new_node;
}

// 查询哈希表中对应key的计数
static int hash_get_count(hash_t *hash, int key) {
    int idx = hash_func(key, hash->size);
    hash_node_t *node = hash->buckets[idx];
    while (node) {
        if (node->key == key) {
            return node->count;
        }
        node = node->next;
    }
    return 0;
}

// 销毁哈希表
static void hash_destroy(hash_t *hash) {
    for (int i = 0; i < hash->size; i++) {
        hash_node_t *node = hash->buckets[i];
        while (node) {
            hash_node_t *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(hash->buckets);
    free(hash);
}

n_t * delFromList(n_t *h, int x) {
    if (h == NULL) return NULL;

    // 1. 创建哈希表统计频次，选101作为桶数（质数减少冲突）
    hash_t *hash = hash_create(101);
    n_t *curr = h;
    while (curr) {
        hash_update_count(hash, curr->val);
        curr = curr->next;
    }

    // 2. 遍历链表删除频次≥x的节点，用哑节点处理头节点删除
    n_t *dummy = malloc(sizeof(n_t));
    dummy->next = h;
    curr = dummy;
    while (curr->next) {
        int count = hash_get_count(hash, curr->next->val);
        if (count >= x) {
            n_t *temp = curr->next;
            curr->next = curr->next->next;
            free(temp);
        } else {
            curr = curr->next;
        }
    }

    n_t *new_head = dummy->next;
    free(dummy);
    hash_destroy(hash);
    return new_head;
}

优化效果说明 #

• 时间复杂度从O(n²)降至O(n)，仅需两次遍历链表，哈希表操作平均为O(1)；
• 空间复杂度为O(k)，不会受元素数值大小影响，避免大数导致的内存浪费；
• 哑节点简化了头节点删除逻辑，无需单独处理头节点的特殊情况。

备选方案（无额外空间，仅适用于短链表） #

如果不允许使用哈希表，可采用标记删除法：

1. 第一次遍历：对每个节点，遍历后续节点统计出现次数，若≥x则将节点值设为特殊值（如INT_MIN）标记；
2. 第二次遍历：删除所有标记的节点。
   该方案时间复杂度仍为O(n²)，仅适合链表较短的场景。

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