In the book, the author introduces many different methods. As the author indicates, the two-pointer iterative solution is the best. In contrast, the recursive method is less effective but quite interesting. It might be useful in some cases. I only implement these two solutions, as iterative and recursive respectively. In both solutions, the return value is the same. The recursive method is as following.
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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-20 11:53 # Filename: 2.2.ite.c # Description: find out the kth latest item in list =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <errno.h> // 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; } struct list *find_kth_latest_rec(struct list *current, const long int target, long int *current_pos ){ // Recursively travel the list from end to begin struct list *temp = NULL; if(current->next == NULL){ // Last element *current_pos = 1; } else{ // Or recursively call this function to travel // the tail nodes temp = find_kth_latest_rec(current->next, target, current_pos); *current_pos += 1; } return *current_pos == target ? current : temp; } struct list *find_kth_latest(struct list *head, long int k){ // This function will return the pointer to the kth // latest items in the list. Or NULL for failure. long int current_pos = 0; // Check the input parameter if( k < 1 || head == NULL || head->next == NULL){ return NULL; } return find_kth_latest_rec(head->next, k, ¤t_pos); } 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, *result = NULL; long int position = 0; char *strtol_res = NULL; // Check the arguments if(argc < 3){ printf("Usage: %s position word1 word2 ...n",argv[0]); return -1; } errno = 0; position = strtol( argv[1], &strtol_res, 10); if( errno == ERANGE || strtol_res != argv[1] + strlen(argv[1]) || position < 1 ){ printf("Invalid argument for position: %sn",argv[1]); printf("Usage: %s position word1 word2 ...n",argv[0]); return -2; } // 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; // Prepare the test linked list if( build_list(head, argv+2) == false){ free_list(head); printf("Fail to build the list.n"); return -2; } // Find the node and print it printf("Original list: "); print_list(head); result = find_kth_latest(head, position); if( result == NULL){ printf("The position %ld is invalid.n", position); } else{ switch(position){ case 1: printf("The latest element is %sn",result->value); break; case 2: printf("The 2nd latest element is %sn",result->value); break; case 3: printf("The 3rd latest element is %sn",result->value); break; default: printf("The %ldth latest element is %sn", position, result->value); break; } } free_list(head); return 0; } |
The iterative method is more effective.
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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-20 11:53 # Filename: 2.2.ite.c # Description: find out the kth latest item in list =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <errno.h> // 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; } struct list *find_kth_latest(struct list *head, long int k){ // This function will return the pointer to the kth // latest items in the list. Or NULL for failure. struct list *former = head, *latter = head; // Check the input parameter if( k < 1 || head == NULL || head->next == NULL){ return NULL; } // Move the former pointer for k steps while( k-- > 0 && former->next != NULL){ former = former->next; } // K should not be greater than the length of the list if( k != -1 ){ return NULL; } // Move the latter pointer for one step latter = latter->next; // Move both pointers untill former reach the end while( former->next != NULL ){ former = former->next; latter = latter->next; } return latter; } 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, *result = NULL; long int position = 0; char *strtol_res = NULL; // Check the arguments if(argc < 3){ printf("Usage: %s position word1 word2 ...n",argv[0]); return -1; } errno = 0; position = strtol( argv[1], &strtol_res, 10); if( errno == ERANGE || strtol_res != argv[1] + strlen(argv[1]) || position < 1 ){ printf("Invalid argument for position: %sn",argv[1]); printf("Usage: %s position word1 word2 ...n",argv[0]); return -2; } // 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; // Prepare the test linked list if( build_list(head, argv+2) == false){ free_list(head); printf("Fail to build the list.n"); return -2; } // Find the node and print it printf("Original list: "); print_list(head); result = find_kth_latest(head, position); if( result == NULL){ printf("The position %ld is invalid.n", position); } else{ switch(position){ case 1: printf("The latest element is %sn",result->value); break; case 2: printf("The 2nd latest element is %sn",result->value); break; case 3: printf("The 3rd latest element is %sn",result->value); break; default: printf("The %ldth latest element is %sn", position, result->value); break; } } free_list(head); return 0; } |