[数据结构]有序单向链表的去重(C语言)

单向链表的去重

问题描述及分析

给定一个有序的链表,去除重复出现的元素,使每个元素只出现一次。例如一个单向链表为 1->1->2->2->3->4->4->∅ , 那么去重后得到的单向链表为 1->2->3->4->∅ 。

这里的链表保证是有序的,所以出现的重复元素都是相邻的,所以对整个链表进行一次遍历,在遍历的过程中删除这些相邻的重复元素即可。
首先,需要一个遍历指针 t 指向当前遍历到的节点,然后定义两个指针分别为 p1p2p1 指向 t 所指向的节点,而 p2 指向此时 p1 的下一个节点,如果 p2 指向节点的值与 p1 的相同,那么直接让 p1next 跳过 p2 指向 p2next 即可。有可能存在相邻很多个元素都相等,所以可以加一个循环,一次性删除多个和 p1 指向的节点的值相等的节点。?

单向链表去重图解

发现相邻重复元素

p1的next跳过p2指向p2的next

free p2, p2指向当前p1的next



核心代码

void Delete_same(Linklist *head) {
	Linklist *t = head->next;           //t遍历指针
	while (t != NULL) {
		Linklist *p1 = t;               //p1指向t的位置
		Linklist *p2 = t->next;         //p2指向p1之后的位置
		//p1和p2永远是相邻的
		while (p2 != NULL) {
			//删除的永远是p2指向的节点
			if (p1->data == p2->data) {
				p1->next = p2->next;    //p1的next跨过删除的指向之前p2的next
				free(p2);
				p2 = p1->next;          //p2再次指向p1的next
			} else {
				p1 = p1->next;          //两个指针同时往后移
				p2 = p2->next;
			}
		}
		t = t->next;
	}
}



完整程序

完整程序源代码

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

typedef int Elemtype;        //数据类型

typedef struct Node {

	Elemtype data;           //结构体数据域
	struct Node *next;       //结构体指针域

} Linklist;

//链表的初始化
Linklist* Initial_linklist(){
	//向系统申请内存
	Linklist *head = (Linklist *)malloc(sizeof(Linklist));
	head->next = NULL;
	return head;
}

//创建初始链表  采用尾插法
void Create_linklist(Linklist *head, int n) {    //头节点(不带数据)
	Linklist *node, *end;                        //普通节点 尾节点
	end = head;                                  //当链表为空时 头尾指向同一个节点
	printf("创建链表输入 %d 个元素:", n);
	for (int i = 0; i < n; i++) {                //n为插入普通节点的个数
		node = (Linklist *)malloc(sizeof(Linklist));
		scanf("%d", &node->data);
		end->next = node;                        //当前end的next指向了新节点node
		end = node;                              //end往后移,此时新的节点变成尾节点
	}
	end->next = NULL;                            //end最后置NULL
}

//打印链表
void Show_linklist(Linklist *head) {
	Linklist *t = head->next;					 //t为遍历指针 访问每个节点数据
	if (t == NULL)
		puts("链表为空");

	while (t != NULL) {
		printf("%d ", t->data);
		t = t->next;
	}
	printf("\n\n");
}

void Delete_same(Linklist *head) {
	Linklist *t = head->next;           //t遍历指针
	while (t != NULL) {
		Linklist *p1 = t;               //p1指向t的位置
		Linklist *p2 = t->next;         //p2指向p1之后的位置
		//p1和p2永远是相邻的
		while (p2 != NULL) {
			//删除的永远是p2指向的节点
			if (p1->data == p2->data) {
				p1->next = p2->next;    //p1的next跨过删除的指向之前p2的next
				free(p2);
				p2 = p1->next;          //p2再次指向p1的next
			} else {
				p1 = p1->next;          //两个指针同时往后移
				p2 = p2->next;
			}
		}
		t = t->next;
	}
}

int main(){
	Linklist *mylist;
	mylist = Initial_linklist();

	Create_linklist(mylist, 10);
	printf("初始状态链表:\n");
	Show_linklist(mylist);

	Delete_same(mylist);
	printf("链表进行去重后:\n");
	Show_linklist(mylist);
}

程序测试运行结果

一切都是命运石之门的选择,本文章来源于博客园,作者:Amαdeus,出处:http://www.cnblogs.com/MAKISE004/p/17018365.html,未经允许严禁转载

本文转载于网络 如有侵权请联系删除

相关文章

  • java后端开发框架有哪些(java后端需要学哪些框架)

    大家好,又见面了,我是你们的朋友全栈君。Javaweb开发框架了解web开发前端–页面的设计、路由、展示—静态资源(HTML、CSS、JS)–web服务器(nginx)–Vue技术栈开发 后端–对外提供(类)RESTful风格的API—数据库交互–web应用服务器(tomcat)–Spring技术栈开发 交互–HTTP协议通信–JSON格式–RESTful风格 javaweb开发框架的变迁SSH——Struts、Spring、HibernateSpring+SpringMVC+Hibernate/ibatisSSM——Spring+SpringMVC+Mybatis——主流Springboot+Mybatis——兴起微服务框架——springboot+dubbo、springcloud——前沿​后端服务器的主要功能接收外界的API请求,解析后去执行数据库操作,最后将数据包装好返回给调用者(当然,中间还包含其他业务逻辑)和数据操作有关的这类框架一般负责和数据库进行连接,负责SQL的处理,以及将查询到的数据映射成指定的java对象。mybatis:易学,SQL手动编写,移植性差,支持动态S

  • Excel,Power Pivot以及PBI不同场景下的数据分组实现方法

    1.普通透视表分组一般如果需要对数据透视表进行分组,数据如图1所示,数据支持的格式为数字格式以及日期格式,如图2和图3所示,文本格式通常无法进行分组组合。但是对于文本字段就无法进行组合了,如图4所示。如果要实现对文本进行分组,例如A和B要作为一组进行统计,则可以在PowerPivot中进行组合。2.PowerPivot透视表中的集合PowerPivot进行分组,最简单的就是通过添加列进行判断后的分组。此外可以通过分析菜单下的“字段、项目和集”菜单操作来进行,如图5所示,可以通过手动对数据项创建集,如图6所示,得到的结果如图7所示。注意:这里会有一个问题,就是总计值的错误,计算的不是展现出来的合计,而是未经筛选前的合计,所以这里需要在选项设置里面进行更改,如图8所示。最终呈现的效果如图9所示,把不存在的进行隐藏并不再计算。3.PowerBI分组在Excel中不管是直接透视表中分组还是使用集合都不能的作为切片器使用,但是在PowerBI中的分组却能实现这个功能,通过事先归类好的组合进行筛选,这样在业务归类上更方便,可以通过新建数据组来对数据进行分组归类,如图10所示。通过数据分组,不仅可以

  • 引领技术变革,腾讯云、腾讯WeTest和英特尔,合作布局云游戏

    作者:wetest小编商业转载请联系腾讯WeTest获得授权,非商业转载请注明出处。原文链接:https://wetest.qq.com/lab/view/397.htmlWeTest导读ChinaJoy作为中国泛娱乐产业年度风向标,受到全球业界的高度关注。在本届ChinaJoy上,腾讯云、腾讯WeTest和英特尔,合作为游戏玩家、游戏开发者等业界人士联合展出了云游戏解决方案Demo。未来,该联合方案的应用将让原本只能在高端配置设备上才能体验的大型游戏,也能流畅运行在入门级设备中。即,游戏玩家能够随时随地,通过手机、平板电脑、台式电脑、电视等任何联网设备,获得一致的高品质游戏体验。云游戏顺应市场需求触发行业增长过去,高品质大型游戏对于终端设备的配置要求之高,一直限制着众多游戏玩家、开发发行商、分发渠道等对此领域的深入探索。根据Steam平台在2018年5月的调查,有约24%的Steam用户电脑内存不足8G,没有达到流畅体验《绝地求生》的最低要求,如果显卡和CPU也同样采用入门款配置就会出现画面卡顿,使用此类大众设备的游戏用户期待体验大型游戏的需求持续存在。腾讯云、腾讯WeTest达成合

  • ubuntu12.04 cuda6 bumblebee安装图解

    花了一些时间,尝试着在ubuntu12.04上安装cuda6.把过程记录下来,给自己和同我一样小白的人以借鉴。 1我要做什么作为一只cuda菜鸟蛋,并没有什么编程基础,还发骚的想学习cuda,还要在linux下使用。各种问题层出不穷。Cuda4是成功安装过的,因为之前的机器太破,没有optimus(Nvidia的一个自动切换显卡的技术,为了省电。),所以很容易成功(在这个帖子里,还是centos上安装的。http://meatball1982.diandian.com/post/2013-01-02/40047119549)。现在,把自己的安装过程记录下来,希望给像我一样的cuda菜鸟蛋们一个帮助,因为网上的安装教程抄来秒去,并没有太具体的问题解决方法(我写的这个安装过程很可能也是这样)。2我的机器和要安装的东西机器:Thinkpadw530,64G的一块SSD。显卡:Nvidia的显卡:NVIDIACorporationGK107GLM[QuadroK1000M]Intel自带的显卡:IntelCorporation3rdGenCoreprocessorGraphicsControl

  • 【Spring实战】—— 16 基于JDBC持久化的事务管理

    前面讲解了基于JDBC驱动的Spring的持久化管理,本篇开始则着重介绍下与事务相关的操作。 通过本文你可以了解到: 1Spring事务管理的机制   2基于JDBC持久化的事务管理 Spring的事务管理的机制  Spring本身并不提供事务管理,它只是把事务管理提交给事务管理器,而事务管理器则有多种实现,常见的就是基于JDBC的、Hibernate的、JPA以及JTA的。  操作流程可以参考下面的图片:  其实还有好多种类的事务管理器,这里就不一一列举了。基于JDBC持久化的事务管理  基于JDBC的持久化,其实就是使用JDBC驱动,在利用spring模板的情况下实现的持久化。  与Hibernate不同的是,它没有一些Session的概念以及实体关联关系等,因此在查询结果的时候,需要手动的进行转换。  其他的方面来说,还是很简单实用的。  下面看一下主要的代码实现流程:  观察上面的实现结构,整个代码在DAO层的实现部分编写,其中包括主要的两个bean,一个是Spring的JDBC模板,一个是事务处理,这两个bean都会依赖于dataSource。  DAO(dataaccess

  • git的入门摸索和入门研究

    git官网:https://git-scm.com/git教程---菜鸟教程:http://www.runoob.com/git/git-tutorial.htmlgit教程---廖雪峰:http://www.liaoxuefeng.com/wiki/0013739516305929606dd18361248578c67b8067c8c017b000/git视频教程---极客学院:http://search.jikexueyuan.com/course/?q=gitgit的安装教程:http://jingyan.baidu.com/article/9f7e7ec0b17cac6f2815548d.html你可以去官网下载git进行window或者linux或者mac的安装;安装之后你可以看文本教程学习,也可以看视频教程学习; 1:用户信息:配置个人的用户名称和电子邮件地址:$gitconfig--globaluser.name"biehl" $gitconfig--globaluser.emailbiehl@koal.com复制2:查看账号信息$gitconfigu

  • 如何利用python制作微信好友头像照片墙?

    这个不难,主要用到itchat和pillow这2个库,其中itchat用于获取微信好友头像照片,pillow用于拼接头像生成一个照片墙,下面我简单介绍一下实现过程,代码量不多,也很好理解,实验环境win10+python3.6+pycharm5.0,主要内容如下,先看一下生成的效果图: 1.首先,下载安装itchat,这是一个微信接口包,专门用于获取微信好友信息,这里我们主要用它来获取微信好友头像信息,安装的话,直接在cmd窗口输入命令“pipinstallitchat”就行,如下: 2.接着,安装pillow,这是python的一个图像处理库,专门用于处理图像,这里我们主要用它来拼接微信好友的头像,生成照片墙,安装的话,与上面类似,直接在cmd窗口输入命令“pipinstallpillow”就行,如下: 3.最后,就是编写代码来实现照片墙制作了,主要代码如下,基本思路就是先用itchat获取微信好友信息,然后根据获取到的UserName信息获取到微信好友的头像,下载到本地image文件夹中,最后再利用pillow一个一个拼接微信好友的头像,生成一个完整的照片墙: 点击运行程

  • 多线程学习笔记(一)

    packagecom.thread; /** *创建一个子线程输出从1~100的自然数 *创建多线程的第一种方式,继承Thread类 *getName获取当前线程的名称 *setName设置当前线程的名称 *start启动子线程 *yield当前线程会释放cpu资源,如果没有其他线程占用那么该线程还会继续执行,如果有其他线程那么可能会被其他线程抢占 *join在A线程中调用B线程的该方法,表示:当A方法执行到该方法时,执行B方法,等待B方法执行完成之后,再继续执行 *isAlive判断当前线程是否还存活 *sleep(longL):显示的让当前线程睡眠L毫秒 *线程通信,waitnotifynotifyAll * *设置线程的优先级 *getPriority()获取当前线程的优先级 *setPriority()设置当前线程的优先级,设置线程的优先级并不会让该线程执行完成之后再执行另一个线程,只能让该线程抢到cpu资源的概率变大,一般默认优先级为5 * *@authorAdministrator * */ publicclassTestThread1{ publicstaticvo

  • hadoop启动缺少NameNode, 缺少ResourceManager, 缺少NodeManager...

    描述:在hadoop运行start-all.sh,发现缺少了NameNode,缺少ResourceManager,缺少NodeManager…等等的服务。这类问题有统一的解决方案。即查阅hadoop日志。 目录 1.hadoop日志2.1没有NameNode(选读)2.2没有ResourceManager和NodeManager(选读)2.3没有ResourceManage(选读)3.总结 1.hadoop日志 hadoop日志位于hadoop安装目录下的logs里,包含了start-all.sh命令中没有显示的重要信息,如果有报错,信息也可以在以下文件中找到。由于我测试了两个host,所以在文件夹里会有两种日志,即以localhost.localdomain.log为结尾的,和以mainnode.log的 2.1没有NameNode 一般来说没有node是由于没有找到是由于忘记格式化namenode,我们输入 [root@mainnodelogs]#vimhadoop-root-namenode-mainnode.log+ 可以查看logs日志找到如下提示。Directo

  • python处理p标签里面多余的class 和 其它标签[html内容处理]

    1、去掉p标签自带的class 2、去掉p标签里面的其他标签 text="""<p><imgsrc="https://www.yikaow.com/upload/images/2019/6/2711221356.jpg"alt="《风雨哈佛路》原型"/></p><pclass="cintro"><spanclass="red">回答</span>《风雨哈佛路》的原型是全美“奇迹女孩”莉兹·默里,讲述的是她从流浪女以自强不息的奋斗精神考上哈佛的励志经历,激励人们跨越困境去追寻心中的梦想。在2003年4月7日的时候,这本图书的同名电影《风雨哈佛路》在美国上映,还获得了第55届艾美奖3项提名。</p>"""复制   步骤 1、使用正则去除p标签 inner_text=re.findall(r'<p[^>]*>(.*?)</p>',text)复制 >>>输出结果 ['<imgsrc="/uploads/images/2019-6-2711

  • 【BZOJ】3453: tyvj 1858 XLkxc 拉格朗日插值(自然数幂和)

    【题意】给定k<=123,a,n,d<=10^9,求: $$f(n)=\sum_{i=0}^{n}\sum_{j=1}^{a+id}\sum_{x=1}^{j}x^k$$ 【算法】拉格朗日插值 【题解】参考:拉格朗日插值法及应用 by DZYO 虽然式子很复杂,但一点一点化简有条理的化简后就可以做了。 首先最后是一个自然数幂和: $$\sum_{x=1}^{j}x^k$$ 这是一个k+1次多项式,可以理解为k+一个Σ(一般一个Σ增加一次项)。 然后会发现最后部分和第二部分之间不需要插值,因为第二部分的前若干小项的计算只需要第一部分的前若干小项,那么: $$g(m)=\sum_{j=1}^{m}\sum_{x=1}^{j}x^k$$ 这是一个k+2次多项式,对g(m)可以O(k)计算前k+2项,因为后面的自然数幂和与j无关,所以可以处理成前缀和(不过对最终复杂度没有意义)。 剩余的部分: $$f(n)=\sum_{i=0}^{n}g(a+id)$$ 这是一个k+3次多项式,强制插值。对于前k+3项,每一项需要O(k)的插值运算,复杂度O(k^2)。 从这道

  • 2019全国大学生信息安全竞赛ciscn-writeup(4web)

    web1-JustSoso php伪协议获取源码 ?file=php://filter/read=convert.base64-encode/resource=index.php index.php 1<html> 2<?php 3error_reporting(0); 4$file=$_GET["file"]; 5$payload=$_GET["payload"]; 6if(!isset($file)){ 7echo'Missingparameter'.'<br>'; 8} 9if(preg_match("/flag/",$file)){ 10die('hackattacked!!!'); 11} 12@include($file); 13if(isset($payload)) 14{ 15$url=parse_url($_SERVER['REQUEST_URI']); 16parse_str($url['query'],$query); 17foreach($queryas$value) 18{ 19if(preg_match("/flag/",$v

  • Element-ui中的给el-row添加一个gutter间隔不生效

    el-row的gutter失效问题完整代码在vue中可直接执行 若想gutter间距效果体现出来,需要将css样式,(如:border,background等),添加在el-col的子标签div中的class下才能生效类名添加在el-col中样式是有了,但是间距确不体现 html代码 <el-row:gutter='20'> <el-col:span='6'><divclass="gutter">132465</div></el-col> <el-col:span='6'><divclass="gutter">132465</div></el-col> <el-col:span='6'><divclass="gutter">132465</div></el-col> <el-col:span='6'><divclass="gutter">132465</div></el-col> &

  • 计应191西第七组杨佳贺

    一、计划做一个小学生一年级口算题卡软件,大概半小时左右完成。 二、开发 需求分析:作为一名一年级小学生的家长,我希望开发出一个口算题卡软件,让我的孩子能在上面练习口算题,能够自动生成一百以内正整数的加减法运算,以便减轻负担。 难点:自动出题、剔除掉减法结果中为负数的情况。 usingSystem;usingSystem.Collections.Generic; usingSystem.Linq; usingSystem.Text; namespaceConsoleAppMath{ classProgram { staticvoidMain(string[]args) { intcount=1;//记录答题数量 interror=0;//记录答题错误数量 do { Randomr=newRandom(); inta=r.Next(0,101);//定义一个初始数0到100,包含100 intb=r.Next(1,3);//定义一个标识,若为1,则计算加法,否则,计算减法 if(b==1){ intc=r.Next(0,100-a);//定义一个和初始数相加小于100的随即数 Con

  • 设计模式-单例模式

    详细讲解请看:http://www.cnblogs.com/cielosun/p/6582333.html 饿汉模式: publicclassSingleton{privatestaticSingletoninstance=newSingleton();privateSingleton(){}publicstaticSingletongetInstance(){returninstance;}}懒汉模式:复制 publicclassSingleton{privatestaticSingletoninstance;privateSingleton(){}publicstaticSingletongetInstance(){if(instance==null)returnnewSingleton();elsereturninstance;}}加锁的的单例:复制 publicclassSingleton{privatestaticSingletoninstance;privateSingleton(){}publicstaticsynchronizedSingletongetInstance

  • UVa10780

    10780AgainPrime?Notime.Theproblemstatementisveryeasy.Givenanumbernyouhavetodeterminethelargestpowerofm,notnecessarilyprime,thatdividesn!.InputTheinputfileconsistsofseveraltestcases.Thefirstlineinthefileisthenumberofcasestohandle.Thefollowinglinesarethecaseseachofwhichcontainstwointegersm(1<m<5000)andn(0<n<10000).Theintegersareseparatedbyanspace.Therewillbenoinvalidcasesgivenandtherearenotmorethat500testcases.OutputForeachcaseintheinput,printthecasenumberandresultinseparatelines.There

  • 转载:百为STM32开发板教程之十一——NOR FLASH

    转载:http://bbs.21ic.com/icview-586199-1-1.html 百为STM32开发板教程之十一——NORFLASH参考文档:百为stm32开发板光盘\st官方参考资料\Applicationnotes\AN2784Usingthehigh-densitySTM32F10xxxFSMCperipheraltodriveexternalmemories.pdf百为stm32开发板光盘\芯片数据手册\M29W128G.pdf百为stm32开发板光盘\芯片数据手册\STM32F10xxx参考手册CD00171190.pdf实验目的:实现擦除和读写M29W128GHNORFLASH的第二个块主要内容:一、了解STM32的FSMC接口二、了解M29W128GHNORFLASH的相关操作三、编程实现擦除并读写M29W128GHNORFLASH的第二个块 一、了解STM32的FSMC接口1、STM32FSMC功能框图:FSMC主要包括有:AHB接口(包含FSMC配置寄存器),NOR闪存和PSRAM控制器,NAND闪存和PC卡控制器,外部设备接口 

  • urllib库在python2和python3环境下的使用区别

    好东西啊!!! Python2name Python3name urllib.urlretrieve() urllib.request.urlretrieve() urllib.urlcleanup() urllib.request.urlcleanup() urllib.quote() urllib.parse.quote()  urllib.quote_plus() urllib.parse.quote_plus() urllib.unquote() urllib.parse.unquote() urllib.unquote_plus() urllib.parse.unquote_plus() urllib.urlencode() urllib.parse.urlencode() urllib.pathname2url() urllib.request.pathname2url() urllib.url2pathname() urllib.request.url2pathname() urllib.getproxies() u

  • 代理

    服务器一般为封闭环境,需要保持足够的稳定,上面的应用应保持洁净,应用的配置文件、启动脚本、静态资源等目录需要合理规划,做到统一。服务器数量越多越要规范,管理起来才有条不紊。服务器的访问问题,鉴于安全原则,入口和出口都需要统一口径,统一入口和出口。跟网关的理念一样,便于管理。因此不管是线下环境还是线上环境,对于服务器外网的开通都需要备案记录。针对服务器需要访问外网才能安装某些软件的场景,应该都走代理。即提供一台可以上外网的机器作为代理服务器,其他的线下或线上资源通过代理进行操作。 常用的代理工具有goproxy,tinyproxy。下面记录一下goproxy的使用,机器ip为:192.168.1.10 goproxy ``` ####方法1 curl-Lhttps://raw.githubusercontent.com/snail007/goproxy/master/install_auto.sh|bash. ``` 复制 ``` ####方法2 cd~/proxy wgethttp://mirrors.host900.com:9090/snail007/goproxy/proxy-l

  • java开发岗位面试整理

    一、Java基础 1.String类为什么是final的 2.HashMap的源码,实现原理,底层结构。 3.说说你知道的几个Java集合类:list、set、queue、map实现类。 4.描述一下ArrayList和LinkedList各自实现和区别 5.Java中的队列都有哪些,有什么区别。 6.反射中,Class.forName和classloader的区别。 7.Java7、Java8的新特性 8.Java数组和链表两种结构的操作效率,在哪些情况下(从开头开始,从结尾开始,从中间开始),哪些操作(插入,查找,删除)的效率高。 9.Java内存泄露的问题调查定位:jmap,jstack的使用等等。 10.string、stringbuilder、stringbuffer区别 11.hashtable和hashmap的区别 13.异常的结构,运行时异常和非运行时异常,各举个例子。 14.String类的常用方法 16.Java的引用类型有哪几种 17.抽象类和接口的区别 18.java的基础类型和字节大小 19.Hashtable,HashMap,ConcurrentHashMa

  • mc.exe的使用

    MC支持本地化。 参考资料   http://blog.csdn.net/seastars_sh/article/details/8228646   http://blog.chinaunix.net/uid-7667983-id-2046541.html

相关推荐

推荐阅读