42.png

    1. /*
    2.     用单链表保存m个整数，节点的结构为[data][next],且|data|<=n。现要求设计一个时间复杂度尽可能高效算法，
    3.     对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
    4.     分析：
    5.         题目中提到时间复杂度尽可能高效，其本上就是暗示我们采用空间换时间的方式。因为数据是小于等于n的，我们可以开辟一块
    6.         大小为n的数组，初始值为0，之后我们遍历链表，节点值既是我们寻找的下标，如果下标所在的数组值为0，则将值变为1，如果
    7.         数组值已经为1，则说明在此之前我们遇见过绝对值相同的元素，故将此节点删除。
    8. */
    9. struct Link {
    10.     union {
    11.         int data;
    12.     }type;
    13.     struct Link *next;
    14. };
    15. #include <stdlib.h>
    16. #include <stdio.h>
    17. #include <math.h>
    18. void deleteRepAbs(Link *h,int n) {
    19.     int *arr = (int *)malloc(sizeof(int)*n);//这里记住大小是sizeof(int)*n，如果只写n是不对的
    20.     for (int i = 0; i < n;i++) {//赋初值0
    21.         *(arr + i) = 0;
    22.     }
    23.     struct Link *pre = h, *p = h->next, *r;
    24.     while (p) {
    25.         if (*(arr+abs(p->type.data))==0) {//首次访问，作上记录
    26.             *(arr + abs(p->type.data)) = 1;
    27.             pre = p;
    28.             p = p->next;
    29.         }
    30.         else {
    31.             r = p->next;
    32.             pre->next = p->next;//删除
    33.             free(p);//释放
    34.             p = r;
    35.         }
    36.     }
    37. }
    38. int main() {
    39.     struct Link *head,*p;
    40.     int n = 100;//我们这里默许创建的链表里的节点值的绝对值<=100
    41.     Link *createLink(int);
    42.     head = createLink(0);//0代表我要创建的链表值类型为int
    43.     deleteRepAbs(head,n);
    44.     p = head->next;
    45.     printf("去重后链表为：");
    46.     while (p) {
    47.         printf("%d ",p->type.data);
    48.         p = p->next;
    49.     }
    50.     return 0;
    51. }