nirmalr
BAN USER// Routine to convert tree into doubly list
// after conversion "right" points to "next" node and "left" points to "prev" node
node_t * toList(node_t *curr, node_t *next) {
if (curr == 0) return next;
curr->right = toList(curr->right, next);
if (curr->right)
curr->right->left = curr;
return toList(curr->left, curr);
}
invoke like this,
head = toList(root, 0);
this routine returns head of the list. head and tail is not linked that can be done easily.
void remove_duplicates(node_t **list) {
while(*list) {
node_t *curr = *list;
if (curr->next && (curr->data == curr->next->data)) {
int data = curr->data;
while(curr && curr->data == data) {
node_t *tmp = curr;
curr = curr->next;
delete tmp;
}
*list = curr;
} else
list = &(*list)->next;
}
}
O(n) algorithm to check anagram :
+++++++++++++++++++++++++++++++++
variant of counting sort can be used here as the range is known.
algorithm :
input : string1, string2 (to be checked)
step 1: allocate two integer array c1[26], c2[26]
step 2: initialize elements of array c1, c2 to zero
step 3 : for each character in string1
increment corresponding element in c1 by one (ex : for 'a', c[0]++)
step 4 : for each character in string2
increment corresponding element in c2 by one (ex : for 'a', c[0]++)
step 5 : compare c1 and c2, if both is same then string1 and string2 are anagram.
for optimization, step 3 and 4 can be merged together as they are independent activities.
Forgot to mention, step 2 can be done in O(n) time using some extra space.
- nirmalr January 03, 2011Reverse the whole sentence, then split it and copy the words from last.
Ex :
Assume string is "I am aabaa"
reverse the string "aabaa ma I"
split it - "aabaa", "ma", "I"
now, copy this words (from last) to new string,
I ma aabaa