删除链表中的重复项
建立一个hash_set，key为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_set中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_set中，则保留此节点，将节点内容添加到hash_set中，继续向后遍历。
这里STL没有hash_set，我直接用set实现的：
方法二：空间优先
解决的思路如下：
建立指针p，用于遍历链表；
建立指针q，q遍历p后面的结点，并与p数值比较；
建立指针r，r保存需要删掉的结点，再把需要删掉的结点的前后结点相接。由此去掉重复值。
下面是相关代码：
#include "list.h"
#include <set>
using namespace std;//借助STL中的set来删除链表中的重复项，比较高效（时间比中间更重要）
//建立STL中的set，key为链表中已经遍历的结点内容，开始时为空
//从头开始遍历链表中的结点：
//如果结点内容已经在set中存在，则删除此结点，继续向后遍历
//如果结点内容不在set中，则保留此结点，将结点内容添加到set中，继续向后遍历
ListNode* del_repeated_nodes(ListNode* pHead){if(pHead == NULL)return pHead;set<int> KeySet;ListNode* pNewHead = pHead;ListNode* pCurNode = pHead;KeySet.insert(pHead->value);while(pCurNode->next){//已经存在则删除if(KeySet.count(pCurNode->next->value)){ListNode* pDelNode = pCurNode->next;pCurNode->next = pCurNode->next->next;delete pDelNode;}else{ //不存在则新增KeySet.insert(pCurNode->next->value);pCurNode = pCurNode->next;}}return pNewHead;
}//使用循环遍历方法：
//1.建立指针pNode，用于遍历链表
//2.建立指针pIterNode，用于遍历pNode之后的结点，并与pNode的值比较
//3.建立指针pDupNode，保存需要删除的结点，再把需要删除的结点的前后结点相接，由此去掉重复值
ListNode* del_duplicate_nodes(ListNode* pHead){ListNode* pNewHead = pHead;ListNode* pNode = pNewHead;while(pNode){//pNode用于遍历链表ListNode* pIterNode = pNode;while(pIterNode->next){//遍历pNode之后的结点，并与pIterNode的值比较if(pIterNode->next->value == pNode->value){ListNode* pDupNode = pIterNode->next;//保存要删除的值pIterNode->next = pIterNode->next->next;delete pDupNode;}elsepIterNode = pIterNode->next;}pNode = pNode->next;}return pNewHead;
}ListNode* Test(ListNode* pHead){printf("The original list is: \n");PrintList(pHead);//这里采用两种方法：前者空间占优，后者时间占优//ListNode* pNewHead = del_duplicate_nodes(pHead);ListNode* pNewHead = del_repeated_nodes(pHead);printf("The del duplicate list is: \n");PrintList(pNewHead);return pNewHead;
}void Test1(){ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(2);ListNode* pNode4 = CreateListNode(2);ListNode* pNode5 = CreateListNode(4);ListNode* pNode6 = CreateListNode(1);ConnectListNode(pNode1,pNode2);ConnectListNode(pNode2,pNode3);ConnectListNode(pNode3,pNode4);ConnectListNode(pNode4,pNode5);ConnectListNode(pNode5,pNode6);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test2(){ListNode* pNode1 = CreateListNode(1);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test3(){Test(NULL);
}int main(int argc, char** argv){Test1();Test2();Test3();return 0;
}
相关文章：
python提取文件名数字_在Python中从文件名提取扩展名
是否有从文件名中提取扩展名的功能？#1楼一种选择可能是与点分开：>>> filename "example.jpeg">>> filename.split(".")[-1]jpeg文件没有扩展名时没有错误：>>> "filename".split(&…
imagick API 中文说明
下面是 imagick API 中文说明 ： imagick 类 imagick::adaptiveblurimage 向图像中添加 adaptive 模糊滤镜 imagick::adaptiveresizeimage 自适应调整图像数据依赖关系 imagick::adaptivesharpenimage自适应锐化图像 imagick::adaptivethresholdimage 基于范围的选择…
利用dom4j将实体类转换为对应的xml报文
利用dom4j生成xml报文 目标格式： <?xml version"1.0" encoding"GBK"?><Packet type"REQUEST" version"1.0"><Head><RequestType>C03</RequestType><UserCode>BOCIJS</UserCode…
JSP--JavaBean
JSP 最强有力的一个方面就是能够使用 JavaBean 组件。 按照 Sun 公司的定义， JavaBean是一个可重复使用的软件组件。实际上 JavaBean 是一种 Java 类，通过封装属性和方法成为具有某种功能或者处理某些业务的对象，简称 Bean。 一个基本的 JSP …
python 速度矢量_最近邻搜索4D空间python快速-矢量化
For each observation in X (there are 20) I want to get the k(3) nearest neighbors.How to make this fast to support up to 3 to 4 million rows?Is it possible to speed up the loop iterating over the elements? Maybe via numpy, numba or some kind of vectoriza…
使用ajax不刷新页面获取、操作数据
在使用jsp或html时，利用ajax达到不刷新页面就可以获取、操作数据。 首先上代码 （htmljs） 在此处需要引入jquery插件 <!-- 这是页面部分 html--> <body><div style"width:100%;height:30px; float:left"><in…
C/C++面试题分享
1、指针和引用的区别？ 答：引用是在C中引入的。它们之间的区别有： （1） 非空区别：指针可以为空，而引用不能为空 （2） 可修改区别：如果指针不是常指针…
js增加属性_前端js基础2
JavaScriptECMAScript(ES):规定了js的一些基础的核心知识(变量、数据类型、语法规范、操作语句等) 3/56/7 说出ES5和ES6的区别？ DOM：document object model 文档对象模型，里面提供了一些属性和方法，可以让我们操作页面中的元素 BO…
附加的操作系统服务
select ：等待I/O实现threading：高层次的线程接口thread：多线程调度dummy_threading:提供threading模块的副本接口dummy——thread：提供thread模块的副本接口mutiprocessing：在全局调度锁下使用子进程mmap：内…
使用myeclipse的第一步
使用myeclipse的第一步 将以下代码copy放在一个包中运行，然后在控制台输入任意字符，回车，然后控制台打印一串密匙，这里你输入的就是账号，控制台返回的就是注册码，点击MyEclipse->Subscription *** 输入…
一道题弄明白二维数组的指针
#include<stdio.h> int main(int args,char ** argv) {int map[3][3]{{1,2,3},{4,5,6},{7,8,9}};int **pMap(int **)map;printf("%d\n",map);//数组的首地址printf("%d\n",*(map1));//数组第二行首地址printf("%d\n",*map1);//数组首行的第…
Linux网络编程--进程间通信（一）
进程间通信简介（摘自《Linux网络编程》p85） AT&T 在 UNIX System V 中引入了几种新的进程通讯方式，即消息队列（ MessageQueues），信号量（ semaphores）和共享内存（ sha…
mysql 行号_PQ获取TABLE的单一值作为条件查询MySQL返回数据
下午，我正爽歪歪地喝着咖啡，看着Power BI每秒钟刷新一次，静静等待某个分公司完成本月绩效任务，自动调用Python在钉钉群中发送喜报：紧接着再次调用Python将Power BI云端报告中的各分公司最新完成率数据和柱状图截图发在…
UUID的使用及其原理
今天敲项目要用UUID，想起之前老师告诉UUID的使用，但没说具体的生成逻辑，于是我进行了百度 首先，UUID的使用： //生成随机的UUID String uuid UUID.randomUUID().toString().replaceAll("-", "")…
链表类型题目需要用到的头文件list.h
下面是后面链表相关题目中需要用到的链表结点的定义和相关操作函数，参见下面的list.h文件： 注意链表结点的定义采用cpp的定义方式，它会被cpp的文件调用。比如后面删除链表重复结点的文件del_repeated_list.cpp中的编译方式： g -…
led计数电路实验报告_「正点原子FPGA连载」第八章 按键控制LED灯实验
1)实验平台：正点原子开拓者FPGA开发板2)本实例源码下载：请移步正点原子官网第八章 按键控制LED灯实验按键是常用的一种控制器件。生活中我们可以见到各种形式的按键，由于其结构简单，成本低廉等特点，在家电、数码产品、…
svn官方备份hot-backup.py强烈推荐
Author:牛班图 Date:2016/05/18 Address:suzhou --- centos 6.7默认安装的python是2.6.6，大家可以先查看一下自己操作系统的python版本，python -v； hot-backup.py是基于python2写的，python3的语法有些地方不一样，所以在…
用js方法做提交表单的校验
基础知识： 原始提交如下： <form action"<%basePath %>puser/register" method"post"><input placeholder"Name" name"realname"> <input type"email" placeholder"Email…
tree类型题目需要用到的头文件tree.h
下面是树类型题目需要用到的头文件tree.h,请包含在cpp文件中编译,而不是放在c文件中编译,比如查找树中两个节点的最低公共父结点的题common_parent_in_tree.cpp,编译它的方法是: g -g common_parent_in_tree.cpp -o common_parent_in_tree 下面是tree.h的内容: #include <…
用easyui动态创建一个对话框
function randomString(len) { len len || 32; var $chars ABCDEFGHJKMNPQRSTWXYZabcdefhijkmnprstwxyz2345678; /****默认去掉了容易混淆的字符oOLl,9gq,Vv,Uu,I1****/ var maxPos $chars.length; var pwd ; for (i 0; i < len; i) { pwd $…
网站收录工具(php导航自动收录源码)_网站如何快速收录，网站不收录怎么办？...
经常有朋友说怎么快速收录，网站不收录怎么收录？？其实，网站不包括一般的新网站数量，没有SEO基础，SEO了解合作伙伴经常会遇到问题，甚至很多人会告诉你，不包括网站引流，导致…
JS Uncaught SyntaxError:Unexpected identifier异常报错原因及其解决方法
最近在写ajax的时候，调用js方法，遇到了Uncaught SyntaxError:Unexpected identifier异常报错，开始搞不清原因，很苦恼。 以为是js方法参数个数和长度的问题，后来发现原来是这样~ 以下是 浏览器窗口的报错 以及 按钮处…
python 打印皮卡丘_Python到底是什么？学姐靠它拿了5个offer
你ZAO吗？最近陌陌发布了一款很有意思的产品——ZAO，这款AI换脸的产品刷爆朋友圈！这款产品火爆到什么程度呢？正在使用ZAO的用户会发现，想要生成一段新的AI换脸视频，已经不是等待几秒、排队第几位的问题&…
有一个1亿结点的树,已知两个结点, 求它们的最低公共祖先!
对该问题,分为如下几种情形讨论: 情形一: 假如该树为二叉树,并且是二叉搜索树, 依据二叉搜索树是排过序的, 我们只需要从树的根结点开始,逐级往下,和两个输入的结点进行比较. 如果当前结点的值比两个结点的值都大,那么最低的公共祖先一定在当前结点的左子树中,下一步遍历当前…
数据库SQL优化大总结之百万级数据库优化方案
1.对查询进行优化，要尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引。 2.应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描，如： select id from t w…
js定时执行函数
方法一: //直接现定义函数 var time window.setInterval(function(){ $(’.lingdao_right’).click(); },5000); 方法二: //执行已经有的函数 var time window.setInterval(‘abc()’,5000); 清除js自动执行 clearInterval(time); //time就是定义时的名称，如上
BST(binary search tree)类型题目需要用到的头文件binary_tree.h
下面是二叉搜索树需要用到的头文件binary_tree.h #include <stdio.h>struct BinaryTreeNode{int value;BinaryTreeNode* pLeft;BinaryTreeNode* pRight; };BinaryTreeNode* CreateBinaryTreeNode(int value){BinaryTreeNode* pNode new BinaryTreeNode();pNode->valu…
终止js程序执行的方法
js终止程序执行的方法共有三种 (一)在function里面（普通js方法） （1）return; （2）return false; (二)非function方法里面（如ajax方法） alert(“发生异常”); throw SyntaxError(); ale…
将BST转换为有序的双向链表!
在二叉树中,每个结点都有两个指向子结点的指针. 在双向链表中, 每个结点也有两个指针,它们分别指向前一个结点和后一个结点.由于这两种结构的相似性, 同时二叉搜索树也是一种排过序的数据结构, 因此在理论上有可能实现二叉搜索树和排序的双向链表之间的转换. 下面的文件BST_to_…
计算机病毒实践汇总五：搭建虚拟网络环境
在尝试学习分析的过程中，判断结论不一定准确，只是一些我自己的思考和探索。敬请批评指正！ 涉及内容： INetSim安装及使用 ApateDNS安装及使用 1. 搭建病毒分析网络环境原因 使用虚拟机作为沙箱能把病毒与外界完全隔离开，…