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.
It specifically said without using a buffer.