Problem
Remove duplicates from an unsorted linked list.
Solution
#include <iostream>
using namespace std;
typedef struct linked_list{
int data;
struct linked_list *next;
}Linked_list;
int list_add(Linked_list **head, int d)
{
Linked_list *l = new Linked_list;
if(l == NULL) return 0;
Linked_list *t = *head;
l->data = d;
l->next = NULL;
if(*head == NULL){
*head = l;
return 1;
}
while(t->next != NULL){
t = t->next;
}
t->next = l;
return 1;
}
int list_remove_dup(Linked_list *head)
{
Linked_list *current;
Linked_list *previous;
linked_list *runner;
linked_list *tmp;
if(head == NULL) return 0;
if(head->next == NULL) return 1;
current = head->next;
previous = head;
while(current != NULL){
runner = head;
while(runner != current){
// remove node if equal
if(runner->data == current->data){
tmp = current;
current = current->next;
previous->next = current;
delete tmp;
break;
}
runner = runner->next;
}
if(runner == current){
current = current->next;
previous = previous->next;
}
}
}
int main(int argc, char* argv[])
{
Linked_list *head = NULL;
Linked_list *l;
list_add(&head, 1);
list_add(&head, 1);
list_add(&head, 2);
list_add(&head, 3);
list_add(&head, 9);
list_add(&head, 4);
list_add(&head, 1);
list_add(&head, 5);
cout << "before" << endl;
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
list_remove_dup(head);
cout << "after remove dup " << endl;
l = head;
while(l!=NULL){
cout << l->data << endl;
l = l->next;
}
return 0;
}
Output
before
1
1
2
3
9
4
1
5
after remove dup
1
2
3
9
4
5