Skip to content

Instantly share code, notes, and snippets.

@honghaoz
Created June 6, 2014 01:57
Show Gist options
  • Save honghaoz/73897ccea7e2137d063b to your computer and use it in GitHub Desktop.
Save honghaoz/73897ccea7e2137d063b to your computer and use it in GitHub Desktop.
Remove duplicates from an unsorted linked list
#include<iostream>
#include<set>
using namespace std;
class Node {
public:
int data;
Node *next;
Node(int dat) {
data = dat;
next = NULL;
}
};
class LinkedList {
public:
Node *head;
Node *tail;
int length;
LinkedList() {
head = NULL;
tail = NULL;
length = 0;
}
~LinkedList() {
destory();
}
Node* createANode(int dat);
void makeAList(int a[], int size);
void insertNodeAt(int dat, int index);
void deleteNodeAt(int index);
void printList(Node *h = NULL);
void destory(Node *h = NULL);
void removeDuplicates() {
set<int> testSet;
pair<set<int>::iterator, bool> result;
Node *tempPrev = NULL;
Node *temp = head;
int i = 0;
while(temp != NULL) {
result = testSet.insert(temp->data);
if (result.second == false) {
temp = tempPrev;
deleteNodeAt(i);
i--;
}
i++;
tempPrev = temp;
temp = temp->next;
}
}
};
Node* LinkedList::createANode(int dat) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = dat;
newNode->next = NULL;
return newNode;
}
void LinkedList::makeAList(int a[], int size) {
if (head != NULL) return;
for (int i = 0; i < size; i++) {
Node *temp = createANode(a[i]);
if (i == 0) {
head = temp;
tail = temp;
length++;
} else {
tail->next = temp;
tail = temp;
length++;
}
}
}
void LinkedList::insertNodeAt(int dat, int index) {
if (index < 0 || index > length) return;
Node *temp = createANode(dat);
Node *insertPPrev = NULL;
Node *insertP = head;
for (int i = 0; i < index; i++) {
insertPPrev = insertP;
insertP = insertP->next;
}
// insert at head
if (insertPPrev == NULL) {
temp->next = head;
head = temp;
// insert at tail
} else if (insertP == NULL) {
insertPPrev->next = temp;
tail = temp;
} else {
insertPPrev->next = temp;
temp->next = insertP;
}
length++;
}
void LinkedList::deleteNodeAt(int index) {
if (index < 0 || index >= length) return;
Node *deletePPrev = NULL;
Node *deleteP = head;
for (int i = 0; i < index; i++) {
deletePPrev = deleteP;
deleteP = deleteP->next;
}
length--;
// the only node is deleted
if (length == 0) {
free(head);
head = NULL;
tail = NULL;
return;
}
// at least one node is there
// delete at head
if (deletePPrev == NULL) {
head = head->next;
free(deleteP);
} else if (deleteP == tail) {
tail = deletePPrev;
tail->next = NULL;
free(deleteP);
} else {
deletePPrev->next = deleteP->next;
free(deleteP);
}
}
void LinkedList::printList(Node *h) {
Node *theHead = NULL;
if (h != NULL){
theHead = h;
} else {
theHead = head;
}
while(theHead != NULL) {
cout << theHead->data << " -> ";
theHead = theHead->next;
}
cout << "NULL\n";
}
void LinkedList::destory(Node *h) {
Node *theHead = NULL;
if (h != NULL) {
theHead = h;
} else {
theHead = head;
}
Node *temp;
while (theHead != NULL) {
temp = theHead;
theHead = theHead->next;
free(temp);
}
head = NULL;
tail = NULL;
length = 0;
}
int main() {
int a[] = {1,2,3,4,5,6,7,8};
LinkedList list = LinkedList();
list.makeAList(a, 8);
list.printList();
list.insertNodeAt(10,8);
list.insertNodeAt(10,2);
list.insertNodeAt(7,2);
list.printList();
list.removeDuplicates();
list.printList();
list.destory();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment