Random4
BAN USERA brute-force solution would be to sort the array and check the number of consecutive elements that are the same. This will give you the frequency list. O(nlogn) solution.
Next, if you know the terms already, for example if you know they are from [0... n] you can have an array of counters. O(n) solution.
Lastly, if you don't know the terms, use a hash table. Initialize the frequency to 1 when you first encounter a new term, and increment by 1 each time you find one more. O(n) solution.
node * intersection_list(node *a, node *b) {
node *head = NULL, *new_node = NULL;
while(a != NULL && b != NULL) {
if(a->data < b->data) {
a = a->next;
} else if(a->data > b->data) {
b = b->next;
} else {
// If equal, add to the new list being created.
new_node = (node *)malloc(sizeof(node));
new_node->data = a->data;
new_node->next = head;
head = new_node;
a = a->next;
b = b->next;
}
}
// If there is need to keep the proper sorting order;
head = reverse_list(head);
return head;
}
node * add_lists(node *h1, node *h2) {
int carry = 0, sum = 0;
node *sum_list = malloc(sizeof(node));
node *sum_list_current = sum_list;
while(h1 != NULL && h2 != NULL) {
sum = h1->data + h2->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h1 = h1->next;
h2 = h2->next;
}
while(h1 != NULL) {
sum = h1->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h1 = h1->next;
}
while(h2 != NULL) {
sum = h2->data + carry;
carry = sum/10;
sum %= 10;
push(&(sum_list_current->next), sum);
sum_list_current = sum_list_current->next;
h2 = h2->next;
}
if(carry > 0) {
push(&(sum_list_current->next), carry);
}
node *next = sum_list->next;
free(sum_list);
return next;
}
- Random4 October 01, 2012