【题目】
原文:
2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?
译文:
从一个未排序的链表中移除重复的项
进一步地,
如果不允许使用临时的缓存,你如何解决这个问题?
【分析】
(1)如果可以使用额外的存储空间,我们就开一个数组来保存一个元素的出现情况。 对于这种情况,最好的解决方法当然是使用哈希表,但令人非常不爽的是C++标准里是没有 哈希表的(java里有)。所以,在这用一个数组模拟一下就好了。但,这里要注意一个问题, 就是元素的边界,比如链表里存储的是int型变量。那么,如果有负值,这个方法就不奏效 了。而如果元素里的最大值非常大,那么这个数组也要开得很大,而数组中大部分空间是用 不上的,会造成空间的大量浪费。
简言之,如果可以用哈希表,还是用哈希表靠谱。
如下代码遍历一遍链表即可,如果某个元素在数组里记录的是已经出现过, 那么将该元素删除。时间复杂度O(n):
(2)
如果不允许使用临时的缓存(即不能使用额外的存储空间),那需要两个指针,cur做正常的迭代,runner指针遍历cur指针之前的所有元素,判断当前元素的值是否已经出现过。如果出现过就删除cur指向的元素。
【代码一】
/*********************************
* 日期:2014-05-17
* 作者:SJF0115
* 题目: Set Matrix Zeroes
* 来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100000
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool Hash[N];
ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
memset(Hash,0,sizeof(Hash));
ListNode* pre = head;
ListNode* cur = head->next;
while(cur != NULL){
//存在重复元素删除
if(Hash[cur->val]){
ListNode* node = cur;
pre->next = cur->next;
cur = cur->next;
delete node;
}
else{
Hash[cur->val] = true;
pre = cur;
cur = cur->next;
}
}
return head;
}
int main(){
int i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};
for(int i = 0;i < 18;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = DeleteDuplicatesFromUnSortedList(head);
ListNode* cur = head->next;
while(cur != NULL){
printf("%d ",cur->val);
cur = cur->next;
}
return 0;
}
【代码二】
/*********************************
* 日期:2014-05-17
* 作者:SJF0115
* 题目: Set Matrix Zeroes
* 来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
ListNode* pre = head;
ListNode* cur = head->next;
//删除重复元素
while(cur != NULL){
ListNode* runner = head->next;
//判断是否是重复
while(runner != cur){
if(runner->val == cur->val){
ListNode* node = cur;
//删除node
pre->next = cur->next;
cur = pre->next;
delete node;
break;
}
runner = runner->next;
}
//如果上面没有删除元素,需要更新指针
if(runner == cur){
pre = cur;
cur = cur->next;
}
}
return head;
}
int main(){
int i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};
//输入
for(int i = 0;i < 18;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
//删除重复元素
head = DeleteDuplicatesFromUnSortedList(head);
//输出
ListNode* cur = head->next;
while(cur != NULL){
printf("%d ",cur->val);
cur = cur->next;
}
return 0;
}
分享到:
相关推荐
主要介绍了python无序链表删除重复项的方法,本文给大家介绍的非常详细,具体一定的参考借鉴价值,需要的朋友可以参考下
输入一组数字,换行,输入要删除的元素,输出删除后的元素和元素个数。若输入字母,浮点型数据可判错。
要求控制台显示如下内容,然后根据前方数字进行相应操作 1、创建一条含整数结点的无序链表 2、链表结点的输出 3、链表结点的升序排序 4、分别计算链表中奇数和偶数结点之和并输出 5、释放链表 0、退出
从键盘输入一组整型元素序列,建立链表。要求输入元素递增,如果不递增提示重新输入刚才错误的数据。 实现该链表的遍历。 在该链表中进行顺序查找某一元素,查找成功返回1,否则返回0。 把元素x插入递增有序表中,...
如果不能使用临时缓存,你怎么实现无序链表中移除重复项(?C和JAVA实例无序链表中移除重复项。
数据结构2.1完整链表代码,适合初接触的大学生。
c语言链表的基本操作 c语言链表的基本操作之删除排序链表中的重复元素
数据结构c语言版链表删除重复节点,包含数据类型、结构的定义和函数的实现
链表相同元素删除 TC和W-TC已运行成功
《数据结构》作业系统题目:按要求删除链表中的元素,并保持链表连续性
删除排序链表中的重复元素 题目 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/ 思路 由于是排序链表,所以只需...
删除排序链表中的重复元素给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例 1:输入: 1->1->2输出: 1->2示例 2:输入: 1->1
删除排序链表中的重复元素.md
删除排序链表中的重复元素 II.md
可快速返回链表的中间元素,算法实现:同时定义两个计数器,之间有2倍的关系,即当一个计数器找到最后一个元素时,另外一个便是中间元素。不过其中有数据类型的转换、数据奇偶的判断。
本小程序是对于循环双向链表中删除指定元素 考虑几种边界情况!
题目链接:删除排序链表中的重复元素给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例 1:输入: 1->1->2输出: 1->2示例 2:输入:
两个无序的单链表合并成一个有序的单链表,链表长度及数据由用户输入。
删除排序链表中的重复元素(java代码).docx