C语言如何修改链表删除元素最后一次出现函数 实现删除最后k次出现

实现思路 #

完全可以在原有删除最后一次出现的函数基础上做少量调整实现目标功能，核心思路如下：

• 原有删除最后一次的逻辑是仅记录最后一个匹配节点的二级指针，扩展后改为记录所有匹配节点的二级指针，最后删除末尾的k个即可
• 需要补充处理边界场景：k小于等于0、无匹配节点、k大于总匹配数时删除所有匹配项
• 删除时需从后往前操作，避免先删除前序节点导致后续存储的二级指针失效

具体实现代码 #

版本1：单次遍历+动态数组存储（改动最小） #

#include <stdlib.h>

void DeleteLastKOccurrences(int x, int k, List *l)
{
    if (k <= 0 || isEmpty(*l)) {
        return;
    }
    int match_count = 0;
    List **match_ptrs = NULL;
    List *p = l;

    // 遍历收集所有匹配节点的二级指针
    while (*p != NULL) {
        if ((*p)->number == x) {
            match_count++;
            match_ptrs = realloc(match_ptrs, match_count * sizeof(List*));
            match_ptrs[match_count - 1] = p;
        }
        p = &(*p)->next;
    }

    if (match_count == 0) {
        free(match_ptrs);
        return;
    }

    // 计算实际需要删除的数量
    int del_cnt = k > match_count ? match_count : k;
    // 从后往前删除避免指针失效
    for (int i = match_count - 1; i >= match_count - del_cnt; i--) {
        depile(match_ptrs[i]);
    }
    free(match_ptrs);
}

版本2：两次遍历无动态内存（适合不允许动态分配的场景） #

如果不想使用动态数组存储指针，可以先遍历一次统计匹配总数量，再第二次遍历删除不需要保留的匹配项：

void DeleteLastKOccurrences(int x, int k, List *l)
{
    if (k <= 0 || isEmpty(*l)) {
        return;
    }
    // 第一次遍历统计总匹配数
    int total_match = 0;
    List tmp = *l;
    while (tmp != NULL) {
        if (tmp->number == x) {
            total_match++;
        }
        tmp = tmp->next;
    }
    if (total_match == 0) {
        return;
    }
    // 计算需要保留的前N个匹配项
    int keep_cnt = total_match - (k > total_match ? total_match : k);
    int current_match = 0;
    List *curr = l;
    while (*curr != NULL) {
        if ((*curr)->number == x) {
            if (current_match >= keep_cnt) {
                depile(curr);
                continue; // 删除后curr已指向下一节点，无需手动移动
            }
            current_match++;
        }
        curr = &(*curr)->next;
    }
}

测试验证 #

用你给出的测试用例验证：

• 输入链表：[2;1;1;2;4;4;4;4]，参数x=4、k=3
• 匹配总数量为4，实际删除3个，最终得到结果[2;1;1;2;4]，完全符合预期
• 若传入k=10（大于总匹配数4），则删除所有4个匹配的4，最终结果为[2;1;1;2]

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