c语言实现链表中重复数据的删除(5)

对比与数组中我们删除重复元素有这么一些方法：

????第一种思路： 遍历要删除的数组arr, 把元素分别放入另一个数组tmp中，在判断该元素在arr中不存在才允许放入tmp中。
时间复杂度为O(n) 空间复杂度为O(1)

????第二种思路： 可以用一个索引标记哪些字符串重复了，重复的取小的索引值
将存储索引值的数组根据索引值把元素打印出来

????第三种思路： 直接使用二重循环，暴力解决出来

????方法一我这里实现链表的重复值删除采用的就是数组中的第三种方法，通过每一次，将链表中的所有元素与第1（2，3，4…）个元素比较，然后删除重复的元素

但是这个时间复杂度是O(n^2)级别，令人堪忧。。。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};

int main(int argc, char const *argv[])
{
    int n, i;
    scanf("%d", &n);
    struct node *head,*tail,*p, *q, *t;
    head = (struct node*) malloc (sizeof(struct node));
    head -> next = NULL;
    tail = head;

    //向单向链表中插入值
    for(i = 0; i < n; i++)
    {
        p = (struct node*) malloc (sizeof(struct node));
        scanf("%d", &p -> data);
        p -> next = NULL;
        tail -> next = p;
        tail = p;

    }
    
    //通过两个指针的遍历来实现删除重复元素。类似于数组里面的双层循环
    p = head -> next;
    while(p -> next != NULL)
    {
        q = p -> next;
        t = p;
        while(q != NULL)
        {
            if( p -> data == q -> data || p -> data == (-1) * (q -> data) )
            {
                q = q -> next;
                t -> next = q;
            }
            else
            {
                q = q -> next;
                t = t -> next;
            }
        }
        if(p -> next == NULL)
        {
            break;
        }
        else
        {
            p = p -> next;
        }
    }
  
    p = head -> next;
    while(p)
    {
        if(p -> next)
        {
            printf("%d ", p -> data);
        }
        else
        {
            printf("%d\n", p -> data);
        }
        p = p -> next;
    }
    return 0;
}

✅方法二 采用类比数组中的第二种思路,建立一个辅助数组，将其初始值都设为-1，遍历链表，若链表值为21，则在辅助数组下标为21的位置让其值加一，以此类推。在加值之前，判断其是否为-1，若不为-1则证明是重复值，此时删掉结点就行（注意，删除需要前驱结点）

这样由于只遍历了一遍链表，所以时间复杂度为O(n)

#include <stdio.h>
#include <stdlib.h>

#define MAX 10000
struct node
{
    int data;
    struct node *next;
};



int main(int argc, char const *argv[])
{
    int aux[MAX];
    for(int k = 0; k < MAX; k++)
        aux[k] = -1;

    int n, i;
    scanf("%d", &n);
    struct node *head,*tail,*p, *q;
    head = (struct node*) malloc (sizeof(struct node));
    head -> next = NULL;
    tail = head;

    //向单向链表中插入值
    for(i = 0; i < n; i++)
    {
        p = (struct node*) malloc (sizeof(struct node));
        scanf("%d", &p -> data);
        p -> next = NULL;
        tail -> next = p;
        tail = p;

    }

    //遍历链表，当数组元素为非-1时，则是要删除的节点
    //因为只有一次链表遍历，所以时间复杂度为O(n)


    q = head;
    while(q != NULL)
    {
        int point;
        if(q -> next -> data < 0) //这样就确保记录了前驱节点
            point = (-1)* (q -> next -> data);
        else
            point = q->next->data;

        if(aux[point] != -1)
        {
            //删除重复的节点
            q->next = q->next->next;

        }
    
        aux[point]++;

        q = q->next;

    }


    //打印出新的链表
     p = head -> next;
    while(p)
    {
        if(p -> next)
        {
            printf("%d ", p -> data);
        }
        else
        {
            printf("%d\n", p -> data);
        }
        p = p -> next;
    }


   

}