Remove Duplicates from a Linked List

Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list.

Implemntation:

```#include <iostream>
using namespace std;
typedef struct ListNode{
int data;
struct ListNode *next;
};

struct ListNode *newNode = new struct ListNode;
if(newNode == NULL)
return 0;
newNode->data = d;
newNode->next = NULL;
return 1;
}
while(t->next != NULL){
t = t->next;
}
t->next = newNode;
return 1;
}

struct ListNode *current;
struct ListNode *previous;
struct ListNode *itr;
struct ListNode *tmp;
return 0;
return 1;
while(current != NULL){
while(itr != current){
// remove node if equal
if(itr->data == current->data){
tmp = current;
current = current->next;
previous->next = current;
delete tmp;
break;
}
itr = itr->next;
}
if(itr == current){
current = current->next;
previous = previous->next;
}
}
}
int main(int argc, char* argv[]){
struct ListNode *ptr;
cout << "Original List" << endl;
while(ptr!=NULL){
cout << ptr->data << endl;
ptr = ptr->next;
}
cout << "After removing duplicates " << endl;
while(ptr!=NULL){
cout << ptr->data << endl;
ptr = ptr->next;
}
return 0;
}

```

Complexity: O(n^2)

If you can sort the list in O(nlogn) then it will take O(nlogn). Post your solution in comments.

0 Thoughts on “Remove Duplicates from a Linked List”

1. Marco Salazar on July 26, 2014 at 6:05 pm said:

It specifically said without using a buffer.