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;
};

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

int RemoveDuplicates(struct ListNode *head){
	struct ListNode *current;
	struct ListNode *previous;
	struct ListNode *itr;
	struct ListNode *tmp;
	if(head == NULL) 
		return 0;
	if(head->next == NULL) 
		return 1;
	current = head->next;
	previous = head;
	while(current != NULL){
		itr = head;
		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 *head = NULL;
	struct ListNode *ptr;
	AddElement(&head, 3);
	AddElement(&head, 2);
	AddElement(&head, 1);
	AddElement(&head, 2);
	AddElement(&head, 2);
	AddElement(&head, 3);
	AddElement(&head, 1);
	AddElement(&head, 5);
	cout << "Original List" << endl;
	ptr = head;
	while(ptr!=NULL){
		cout << ptr->data << endl;
		ptr = ptr->next;
	}
	RemoveDuplicates(head);
	cout << "After removing duplicates " << endl;
	ptr = head;
	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.

One Thought 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation