企业官网建设流程全解析

这道题给一条带头结点的单链表，里面有m个整数，每个数满足数学意义上的|data|≤n。相同绝对值只保留第一次出现的结点，后面再出现就删除。

比如：

原链：21 → -15 → -15 → -7 → 15 结果：21 → -15 → -7

第二个-15当然重复，最后的15也重复，因为我们比较的是绝对值。要留下的是原来的第一个-15结点，不是重新造一个15放进去。

我先看到了这个范围

这题我最开始就想到开一个数组。既然绝对值不会超过n，可以让每个绝对值占一个位置，记录它有没有出现过。

比如读到-15，就看seen[15]；读到15，也看seen[15]。第一次见到时，把这一格从0改成1；以后再看到1，就知道该删了。

没有这张表也能做：每来一个结点，回头检查前面保留的结点。只是链表本来要从前往后处理，现在每一步又要从头找一遍。没有重复时，比较次数从0、1、2一直加到m-1，最坏是O(m²)。

我开数组就是想省掉这个“回头找”。这次不是拿绝对值和前面所有数比较，而是直接查它对应的那一格。

这里得分清n和m。n是取值上界，不是链表长度。原例只有5个结点，但要访问seen[21]，数组只开5格肯定不够。

下标从0到n，一共n+1格。0也能作为数据出现，seen[0]要留着；第一份0保留，后面的0同样要删。表开始全部是0。

查表会了，怎么把结点删掉？

换一串小一点的，方便把指针走清楚：

头 → 1 → 2 → -2 → 2 → 3 → NULL

两个值为2的结点不是同一个，后面分别叫它们“前面的2”和“后面的2”。

我用cur检查当前结点，用pre指向它的前驱。开始pre在头结点，cur在1。头结点不是数据，不查seen；但它能帮我们统一改首结点前面的连接。

先读1：seen[1]是0，把它改成1，保留这个结点。下一轮cur要检查2，那么pre就应该到刚保留的1。

再读前面的2：也是第一次，seen[2]改成1。于是pre来到这个2，cur来到-2。

读到-2时，seen[2]已经是1。这回不是让pre到cur，而是改pre.next，让它绕过-2，直接指向后面的2。

删除前：前面的2 → -2 → 后面的2 → 3 删除后：前面的2 ─────→ 后面的2 → 3 pre cur

这时cur已经换成后面的2，pre还在前面的2。它仍然正好是cur的前驱。

接着查后面的2，seen[2]还是1，所以再删一次。同一个pre又把next改成3。到3时才首次出现，保留3，pre才向后移动。

最终就是1→2→3。

为什么删除以后pre不能跟着走？

看刚才删掉-2后的状态。前面的2还在，它的next已经接到了下一个待检查结点，pre不用另找位置。

如果这时把pre也移到后面的2，再从pre.next开始检查，就直接去看3了。后面的2还没查表，却被当成已经处理完的结点，结果留下两个2。

不是说所有指针都不能动：cur必须换成下一结点，不能再停在被删掉的结点上。两条分支的区别是，保留cur时，pre移到cur；删除cur时，pre保持原位。

seen[2]也不能因为删掉-2就清成0。前面首次出现的2仍在链里，后面的2仍要按重复处理。这张表记录的是已经出现过哪些绝对值，不是当前结点是否还存在。

把删除的几步写在一起

删cur前，先用next存好cur.next，再让pre.next=next，之后才free(cur)。下一轮令cur=next。

这样下一结点的地址在释放前已经拿到了。不能先free(cur)，再去读cur.next；释放以后，cur指向的内存就不能继续访问。

图中A和C都存2，但它们是两个结点。B被释放后，C还是原来的C，不会因为少了一个结点就变成B。next里保存的是C的地址，不是一份新结点；所以B释放了，我们仍能用它让cur来到C。此时pre仍在A，C还没检查，下一轮查seen[2]才能决定把C也删掉。

#include <stdint.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; int deduplicate(Node *head, int n) { if (!head || n < 0) return 0; unsigned char *seen = calloc((size_t)n + 1, sizeof(*seen)); if (!seen) return 0; Node *pre = head, *cur = head->next; while (cur) { size_t key = (size_t)(cur->data < 0 ? -(int64_t)cur->data : (int64_t)cur->data); /* Input contract: absolute value of each data item is at most n. */ if (!seen[key]) { seen[key] = 1; pre = cur; cur = cur->next; } else { Node *next = cur->next; pre->next = next; free(cur); cur = next; } } free(seen); return 1; }

循环中，没见过就置标记、保留并移动pre；见过就绕开、释放，只移动cur。顺着上面的五轮，正好能对应这两个分支。

返回1表示处理完成。seen分配失败就返回0，此时还没进入删除循环，原链没改；传空头指针或负上界也返回0。空数据链但头结点有效，可以正常完成。

这份程序会free重复结点，所以数据结点须是能分别释放的动态分配结点，不能把栈上的结点或整块数组中的单个元素传进来释放。输入还须无环，且每个绝对值不超过n；程序按题目的范围查表，并不额外检查越界数据。

取绝对值的表达式先转成int64_t再取负，避免在常用32位int环境里直接对最小负整数取负而溢出。但范围前提仍然要满足，不能因此拿超出n的值去索引seen。原题n为正，代码也兼容n=0。

每个原结点只检查一次，保留或删除都不回退，链表处理是O(m)。但n+1格表也要初始化，不能因为只有几份数据就忽略整张表的成本，所以总时间是O(m+n)，额外空间是O(n)。

如果取值范围特别大，而链表只有几个结点，这张表就不一定合算；这里之所以能直接按值查表，靠的是题目给出的范围条件。链表本身并不需要有序，也不需要为了去重重新排序。

题意按2015年408原卷第41题整理，原卷来自厦门工学院公开备考资料。下面保留我的解题复盘，C实现与验证是补充，不是官方答案。

附录：完整验证程序

参照记录每个绝对值首次出现的地址，比较结果链。连续重复、零、负值都有覆盖；释放后由内存检查辅助确认。分配失败分支的处理约定在实现里明确，批量用例不等于模拟了所有分配失败。

完整程序包含上面的题解函数和独立参照。保留源码，是为了读者能自己改输入、定位错误，不需要先读完它才能理解正文。

gcc -std=c11 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined -fno-omit-frame-pointer lab.c -o lab ./lab

#include <assert.h> #include <limits.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; int deduplicate(Node *head, int n) { if (!head || n < 0) return 0; unsigned char *seen = calloc((size_t)n + 1, sizeof(*seen)); if (!seen) return 0; Node *pre = head, *cur = head->next; while (cur) { size_t key = (size_t)(cur->data < 0 ? -(int64_t)cur->data : (int64_t)cur->data); /* Input contract: absolute value of each data item is at most n. */ if (!seen[key]) { seen[key] = 1; pre = cur; cur = cur->next; } else { Node *next = cur->next; pre->next = next; free(cur); cur = next; } } free(seen); return 1; } int main(void) { size_t cases = 0; for (int length = 0; length <= 7; length++) { size_t total = 1; for (int j = 0; j < length; j++) total *= 5; for (size_t mask = 0; mask < total; mask++) { Node head = {0, NULL}, *tail = &head; Node *kept[3] = {NULL, NULL, NULL}; int expected[3], count = 0; size_t x = mask; for (int j = 0; j < length; j++) { Node *p = malloc(sizeof(*p)); assert(p); p->data = (int)(x % 5) - 2; x /= 5; p->next = NULL; tail->next = p; tail = p; int key = p->data < 0 ? -p->data : p->data; if (!kept[key]) { kept[key] = p; expected[count++] = key; } } assert(deduplicate(&head, 2)); Node *p = head.next; for (int j = 0; j < count; j++) { assert(p == kept[expected[j]]); p = p->next; } assert(p == NULL); p = head.next; while (p) { Node *next = p->next; free(p); p = next; } cases++; } } Node h = {0, NULL}; assert(deduplicate(&h, 0)); assert(!deduplicate(NULL, 2)); printf("PASS dedup cases=%zu\n", cases); return 0; }

这次改写后，重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序，97656组小范围链表枚举检查通过，输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。

PASS dedup cases=97656

有限测试是发现错误的证据，不代替正文的正确性与复杂度理由。