首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >设计在单链表中删除值相同的多余结点的算法

设计在单链表中删除值相同的多余结点的算法

作者头像
wangweijun
发布2022-01-10 15:47:29
2.1K0
发布2022-01-10 15:47:29
举报
文章被收录于专栏:wangweijunwangweijun

这是一道算法题,写算法题最恨没有图解,懂的人不需要看你的文章,不懂的你再怎么讲解也没有几张图解来得简单易懂,下面来分析一下这道题。

我暂时还没有更好的解决方案,虽然有一个办法解决,但是时间复杂度有点高,先看看我的思路吧。

在这里插入图片描述
在这里插入图片描述

这是一个无序的单链表,我们采用一种最笨的办法,先指向首元结点,其元素值为2,再遍历该结点后的所有结点,若有结点元素值与其相同,则删除;全部遍历完成后,我们再指向第二个结点,再进行同样的操作。

看图解:

在这里插入图片描述
在这里插入图片描述

这里有两个指针变量p、q,均指向单链表的首元结点,我们先不移动指针p,而是让指针q去遍历之后的所有结点。

在这里插入图片描述
在这里插入图片描述

先让指针p指向的结点与后一个结点比较,这里为了操作方便,我们暂且先不移动指针q,而是这样进行比较:p -> data == q -> next -> data;若不相等,则让q指向下一个结点:p = p->next;若相等,则应该先保存下一个结点:r = q -> next,然后让q指针指向下一个结点的下一个结点:q = r -> next,并释放r指向的结点内存。

这样就成功删除了一个与首元结点重复的结点,接下来以同样的方式继续比较,直到整个单链表都遍历完毕,此时单链表中已无与首元结点重复的结点;然后我们就要修改p指针的指向,让其指向首元结点的下一个结点,再让q指向其下一个结点,继续遍历,将单链表中与第二个结点重复的所有结点删除。以此类推,直至指针p也遍历完了整个单链表,则算法结束。

刚才我们已经删除了一个结点,那么接下来p应该指向下一个结点了:

在这里插入图片描述
在这里插入图片描述

此时让指针p指向的结点与下一个结点的元素值比较,发现不相等,那么让q直接指向下一个结点即可:q = q -> next

在这里插入图片描述
在这里插入图片描述

继续让q指向的结点的下一个结点与p指向的结点的元素值比较,发现不相等,此时继续移动q,移动过后q的指针域为NULL,说明遍历结束,此时应该移动指针p。

在这里插入图片描述
在这里插入图片描述

通过比较发现,下一个结点的元素值与其相等,接下来就删除下一个结点即可:

在这里插入图片描述
在这里插入图片描述

此时p的指针域也为NULL,算法结束。

代码如下:

LinkList DeleteRepeat(LinkList l){
	LinkList p,q,r;
	p = l->next;
	while(p != NULL){
		q = p;
		while(q->next != NULL){
			if(p->data == q->next->data){
				r = q->next;
				q = r->next;
				free(r);	
			}else{
				q = q->next;
			}
		}
		p = p->next;
	}
	return l;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-04-12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档