本文主要是介绍CareerCup之2.1无序链表删除重复元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目】
原文：
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 100000struct 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;//删除nodepre->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;
}
这篇关于CareerCup之2.1无序链表删除重复元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
