|
166. How do you remove duplicates from a list.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
166. How do you remove duplicates from a list.....
Question:
How do you remove duplicates from a list.
1. list is sorted
2. list is not sorted
maybe an answer:
1. when the list is sorted
void removeDuplicatesFromSortedList(node* list)
{
node* current = list;
node* nextNext = NULL;
while(current->next != NULL)
{
if(current->val == current->next->val)
{
nextNext = current->next->next;
free(current->next);
current->next = nextNext;
}
else
{
current = current->next;
}
}
}
2. When the list is not sorted.
Use hash table to find the duplicates. Two pointers are required to traverse thru' the list.
For unsorted: a hashtable may require too much memory, but it is fast for lookups. Using a tree structure instead will be more efficient with memory but lookups will require O(logn). This does not affect the overall time complexity of O(n).
(Continued on next question...)
Other Interview Questions
| 