There are two solutions for this question. The first one is with hash table, thus needs more space but less time. The second one needs no additional space but more time.
In the first solution, I choose to use the uthash library, because its simplicity. With hash table, the time used to find duplicate item would be O(1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-16 11:14 # Filename: 2.1.hash.c # Description: remove the duplicate items in the singly linked list =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include "uthash.h" // for hash table use struct hash_table{ char *id; // key int value; UT_hash_handle hh; // makes this structure hashable }; // for the singly linked list struct list{ char *value; struct list *next; }; bool build_list(struct list *current, char *words[]){ // This function build a singly linked list from the words // On success, it return true; otherwise false. char **word = words; if(current->next != NULL){ printf("Warming: truncate a list to build a new one.n"); } while( *word != NULL){ current->next = (struct list *)malloc(sizeof(struct list)); if(current->next == NULL){ printf("Fail to allocate memory.n"); return false; } current = current->next; current->value = *word; current->next = NULL; ++word; } return true; } void free_list(struct list *head){ // This function iteratively travel the singly linked list // and free every node in the list. struct list *current=head, *next=NULL; while(current != NULL){ next = current->next; free(current); current = next; } return; } void del_duplicate(struct list *head){ // This function will remove the duplicate items in the list. struct hash_table *ht=NULL,*current=NULL,*temp=NULL; struct list *node_temp=NULL; while(head->next != NULL){ HASH_FIND_STR( ht, head->next->value, temp); if(temp != NULL){ // If the item is found in the hash table, remove it temp->value += 1; node_temp = head->next->next; free(head->next); head->next = node_temp; } else{ // If the item is not in the hash table, add it to table temp = (struct hash_table*)malloc(sizeof(struct hash_table)); temp->id = head->next->value; temp->value = 1; HASH_ADD_KEYPTR( hh, ht, temp->id, strlen(temp->id), temp ); head = head->next; } } // free the hash table contents HASH_ITER(hh, ht, current, temp) { HASH_DEL(ht, current); free(current); } return; } void print_list(struct list *head){ // print the singly linked list in a pretty manner struct list * temp = head; if(temp == NULL){ printf("The list is invalid.n"); return; } if(temp->next == NULL){ printf("The list is empty.n"); return; } temp = temp->next; printf("%s",temp->value); while(temp->next != NULL){ temp = temp->next; printf(" -> %s",temp->value); } printf("n"); return; } int main(int argc, char *argv[]){ struct list *head=NULL; // Check the arguments if(argc < 2){ printf("Usage: %s word1 word2 ...n",argv[0]); return -1; } // prepare the head node head = (struct list *)malloc(sizeof(struct list)); if(head == NULL){ printf("Fail to allocate memory.n"); return -1; } head->value = NULL; head->next = NULL; if( build_list(head, argv+1) == false){ free_list(head); printf("Fail to build the list.n"); return -2; } printf("Original list: "); print_list(head); del_duplicate(head); printf("Unique list: "); print_list(head); free_list(head); return 0; } |
In the second solution, I did not use hash table. Thus its time complexity is O(n^2), and space complexity is O(1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-16 11:02 # Filename: 2.1.nohash.c # Description: remove the duplicate items in the singly linked list without any additional space =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #define MAXLEN 0xFF // for the singly linked list struct list{ char *value; struct list *next; }; bool build_list(struct list *current, char *words[]){ // This function build a singly linked list from the words // On success, it return true; otherwise false. char **word = words; if(current->next != NULL){ printf("Warming: truncate a list to build a new one.n"); } while( *word != NULL){ current->next = (struct list *)malloc(sizeof(struct list)); if(current->next == NULL){ printf("Fail to allocate memory.n"); return false; } current = current->next; current->value = *word; current->next = NULL; ++word; } return true; } void free_list(struct list *head){ // This function iteratively travel the singly linked list // and free every node in the list. struct list *current=head, *next=NULL; while(current != NULL){ next = current->next; free(current); current = next; } return; } void del_duplicate(struct list *head){ // This function will remove the duplicate items in the list. struct list *runner=NULL, *node_temp=NULL; while(head->next != NULL){ // Travel each node runner = head->next; while(runner->next != NULL){ // Travel all nodes after current position if(strncmp(runner->next->value, head->next->value, MAXLEN)==0){ node_temp = runner->next->next; free(runner->next); runner->next = node_temp; } else{ runner = runner->next; } } head = head->next; } return; } void print_list(struct list *head){ // print the singly linked list in a pretty manner struct list * temp = head; if(temp == NULL){ printf("The list is invalid.n"); return; } if(temp->next == NULL){ printf("The list is empty.n"); return; } temp = temp->next; printf("%s",temp->value); while(temp->next != NULL){ temp = temp->next; printf(" -> %s",temp->value); } printf("n"); return; } int main(int argc, char *argv[]){ struct list *head=NULL; // Check the arguments if(argc < 2){ printf("Usage: %s word1 word2 ...n",argv[0]); return -1; } // prepare the head node head = (struct list *)malloc(sizeof(struct list)); if(head == NULL){ printf("Fail to allocate memory.n"); return -1; } head->value = NULL; head->next = NULL; if( build_list(head, argv+1) == false){ free_list(head); printf("Fail to build the list.n"); return -2; } printf("Original list: "); print_list(head); del_duplicate(head); printf("Unique list: "); print_list(head); free_list(head); return 0; } |