C语言实现无序单链表去重

淡淡的烟草味﹌ 2022-12-27 14:04 159阅读 0赞

### 前言 ###

对于无序单链表去重，目前我有两种思路

1.  两层while，主节点和其他节点挨个比对，遍历时，保存前驱其他节点，碰到相同的删除就可以了，时间复杂度是O（n2）
2.  设置flag数组打表，遍历链表且保存前驱，如果第一次碰到该元素，则标记为1，如果再次碰到这个元素则删除就可以，时间复杂度是O（n）,缺点就是打表的缺点，无法顾及到所有的数，当数很大时，空间开销大。

这里我使用第一种方法。惯例，单链表使用带头节点，方便操作。

### 实现 ###

构建单链表

typedef struct ListNode{
        
        struct ListNode *next;
        int data;
    }ListNode,*LinkedList;

创建一个单链表并返回

LinkedList createLinkedList()
    {
        
        LinkedList L = (ListNode*)malloc(sizeof(ListNode));
    	ListNode *r=L;
    	int temp;
    	scanf("%d",&temp);
    	while(temp!=99999)
    	{
        
    	     ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    	     s->data=temp;
    	     r->next=s;
    	     r=s;
    	     scanf("%d",&temp);
    	}
    	r->next=NULL;
    	return L;
    }

打印单链表函数

void printLinkedList(LinkedList L)
    {
        
        ListNode *p = L->next;
        while(p!=NULL)
        {
        
            printf("%d ",p->data);
            p= p->next;
        }
        printf("\n");
    }

主函数实现如下

int main(void)
    {
        
    
        LinkedList L  = createLinkedList();
        printLinkedList(L);
    
        ListNode *p=L->next; // 主节点，初始为第一个元素
        ListNode *pre=NULL;//保存被比较元素的前驱，便于删除
        ListNode *r=NULL; //用于遍历其他节点。
        ListNode *t=NULL; // 用于删除节点
        while(p!=NULL)
        {
        
            r = p->next;
            pre = p;
            while(r!=NULL)
            {
        
                if(r->data==p->data)//元素相同则直接让前驱指向r的后缀
                {
        
                    pre->next = r->next;
                    t = r; //注意回收
                    r = r->next;//接着遍历其它节点
                    free(t);
                }
                else//元素不相同让r向后继续遍历，主节点不变
                {
        
                    pre = pre->next;
                    r = r->next;//接着遍历其它节点
                }
    
            }
            p = p->next;//主节点比对完毕，更换为下一个
        }
        printLinkedList(L);
        return 0;
    }

效果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/63f2b9fae9e945e19e2ff7023a81c55d.png