-
-
Save StephanieMak/c1fbaa95b063b5edcd74 to your computer and use it in GitHub Desktop.
Careercup 2.1 - Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed? Note: 1. pay special attention to deleting a node 2. learn to use "map" in C++ STL as a hash table
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*Remove duplicates from an unsorted linked list - cc2.1*/ | |
void removeDuplicate1(node *head){ | |
map<int,bool> table; | |
node *curr = head; | |
node *pre = NULL; | |
while(curr!=NULL){ | |
/*delete the node if it already exists in the map*/ | |
if(table[curr->data]){ | |
pre->next = curr->next; | |
delete curr; | |
curr = pre->next; | |
} | |
/*add the node to the table if it does not exist in the map before*/ | |
else{ | |
table[curr->data] = true; | |
pre = curr; | |
curr = curr->next; | |
} | |
} | |
} | |
void removeDuplicate2(node *head){ | |
node *curr = head; | |
while(curr!=NULL){ | |
node *runner = curr->next; | |
node *pre = curr; | |
while(runner!=NULL){ | |
if(curr->data == runner->data){ | |
pre->next = runner->next; | |
delete runner; | |
runner = pre->next; | |
} | |
else{ | |
pre = runner; | |
runner = runner ->next; | |
} | |
} | |
curr = curr->next; | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment