链表去重函数时间复杂度疑问：O(n²)还是O(n)？

你写的这个链表去重函数，关于时间复杂度的两种判断，得结合输入场景具体分析，不能一概而论：

你的初始判断（O(n²)）是最坏场景下的正确结论 #

当链表中所有元素都是唯一的时，k（已记录的唯一元素数量）会从1逐步增加到n（链表总长度）。此时内层for循环的总执行次数是1+2+3+...+(n-1) = n(n-1)/2，对应的时间复杂度就是O(n²)，这完全符合算法复杂度分析中「最坏情况」的判断标准。

Tabnine的说法存在局限性 #

Tabnine认为k是常数、内层循环为O(1)，这个结论仅在链表中唯一元素数量远小于n的场景下成立（比如链表只有固定几种重复值）。但k本质是和输入规模相关的变量：它的取值范围是1到n，完全由输入链表的元素分布决定，并非固定不变的常数，所以不能直接将内层循环复杂度定为O(1)。

分场景明确时间复杂度 #

• 最好情况：链表中除第一个元素外全是重复值，k始终为1，内层循环每次仅执行1次，总时间复杂度为O(n)。
• 最坏情况：链表元素全唯一，如前文所述，时间复杂度为O(n²)。
• 平均情况：假设链表中唯一元素数量为k，总执行次数为O(nk)。如果k和n成正比（比如随机生成的链表），复杂度就是O(n²)；如果k是固定常数，复杂度就是O(n)。

优化建议 #

如果想把时间复杂度稳定在O(n)，可以用哈希集合（C语言中可自行实现简单哈希表，或借助第三方库的哈希结构）替代数组存储已出现的元素，这样查找元素是否存在的操作能从O(k)降到O(1)，整体效率会显著提升。

附你的实现代码：

void remove_dupes(struct node * head){
    if(head == NULL || head->next == NULL){return;
    }

    int *nums = malloc(1*sizeof(int));
    int k = 1; int max = 1;
    nums[0] = head->value; struct node *prev = head;
    head = head->next;

    while(head){ 
        int flag = 1;
        for (int i = 0; i<k;i++){ //runs k times where k is the # of unique elemnts in the list
            if (nums[i] == head->value){
                flag = 0;
            }
        }

        if(flag){
            k +=1;
            if(k>max){
                max = max*2;
                nums = realloc(nums,sizeof(int)*max);
            }
            nums[k-1]= head->value; prev = head; head = head->next;
        }
        else{
            prev->next = head->next; free(head); head= prev->next;
        }
    }
}

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