There is a similar and easier question: how to check if an array is a palindrome? Or equivalently, how to check if a double linked list is a palindrome? The three solutions in the original question work well for these two similar questions. But in a better manner, we could set a pointer to the first item and a pointer to the last item. Then we would move the former pointer forward and the latter one backward, until they meet. Before each moving, we compare the value of two “current” items, and return false if they are different. When the two pointers meet, we could return true.
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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-05-11 03:11 # Filename: 2.7.c # Description: check whether the list is palindrome. =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> // for the singly linked list struct list{ char value; struct list *next; }; bool build_list(struct list *head, char *content); void free_list(struct list *head); void print_list(struct list *head); size_t len_of_list(struct list *head); // The three methods to determine the palindrome list bool isPalindrome_rev_comp(struct list *head); bool isPalindrome_ite(struct list *head); bool isPalindrome_rec(struct list *head); bool isPalindrome_rec_helper(struct list *head, size_t len, struct list **tail); bool build_list(struct list *head, char *content){ // This function build a singly linked list from the integer // in backward order. For example, the number 123 could // be a list as head->3->2->1 // On success, it return true; otherwise false. struct list *previous =head, *current = NULL; char *item = content; if( head == NULL ){ return false; } if( head->next != NULL ){ printf("Warming: truncate a list to build a new one.n"); head->next = NULL; } while( *item != ' '){ current = (struct list *)malloc(sizeof(struct list)); if(current == NULL){ printf("Fail to allocate memory.n"); free_list(head->next); return false; } previous->next = current; current->value = *item; current->next = NULL; previous = current; ++item; } 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 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("%c",temp->value); while(temp->next != NULL){ temp = temp->next; printf(" -> %c",temp->value); } return; } size_t len_of_list(struct list *head){ // This function would count the length of a list with head // node. size_t len=0; if(head == NULL){ return -1; } while(head->next != NULL){ head = head->next; ++len; } return len; } bool copy_n_reverse(struct list *original, struct list **target){ // Make a deep and reversed copy of the original list struct list *node =NULL; node = (struct list *)malloc(sizeof(struct list)); if(node == NULL){ return false; } node->value = original->value; node->next = NULL; if(original->next == NULL){ (*target)->next = node; *target = (*target)->next; return true; } else{ if( !copy_n_reverse(original->next, target) ){ return false; } else{ (*target)->next = node; *target = (*target)->next; return true; } } } bool isPalindrome_rev_comp(struct list *head){ struct list reversed = {.value = ' ', .next = NULL}; struct list *preversed = &reversed; bool result; if(head == NULL){ // Invalid list return false; } if(head->next == NULL){ // Empty list return true; } result = copy_n_reverse(head->next, &preversed); if(result == false){ free_list(reversed.next); return false; } preversed = &reversed; while( preversed->next != NULL ){ head = head->next; preversed = preversed->next; if(head->value != preversed->value){ free_list(reversed.next); return false; } } free_list(reversed.next); return true; } bool isPalindrome_ite(struct list *head){ size_t len = len_of_list(head); char *stack = NULL; int stack_index = 0; if(head == NULL){ // Invalid list return false; } if(head->next == NULL){ // Empty list return true; } stack = (char *)malloc(len/2); if(stack == NULL){ return false; } // Store the first part in the stack head = head->next; // Skip the head node while(stack_index < len/2){ stack[stack_index++] = head->value; head = head->next; } if( len%2 == 1 ){ // There are odd number of nodes in the list // Skip the middle node. head = head->next; } while(head != NULL){ if( head->value != stack[--stack_index] ){ free(stack); return false; } head = head->next; } free(stack); return true; } bool isPalindrome_rec_helper(struct list *head, size_t len, struct list **tail){ bool result = false; if(len == 1){ (*tail) = head->next; return true; } else if(len == 2){ (*tail) = head->next->next; return head->value == head->next->value; } else{ result = isPalindrome_rec_helper(head->next, len-2, tail); if( result == false ){ return false; } else{ result = (head->value == (*tail)->value); (*tail) = (*tail)->next; return result; } } } bool isPalindrome_rec(struct list *head){ size_t len = 0; struct list *temp = NULL; len = len_of_list(head); if(len <0){ return false; } if(len == 0){ // Empty list return true; } return isPalindrome_rec_helper(head->next, len, &temp); } int main(int argc, char *argv[]){ struct list test = {.value = ' ', .next = NULL}; bool result = false; // Check the arguments if(argc != 2){ printf("Usage: %s list_contentn",argv[0]); printf("Example: %s aBcdcn",argv[0]); printf(" List: a->B->c->d->c (case sensitive)n"); return -1; } // Prepare the list if( !build_list(&test, argv[1])){ printf("Fail to build the test list: %sn", argv[1]); return -2; } printf("The original list: "); print_list(&test); printf("n"); result = isPalindrome_rev_comp(&test); printf("According to the reverse and compare method:n"); printf(" The list %s palindrome.n",result ? "is" : "is not"); result = isPalindrome_ite(&test); printf("According to the iterative method with stack:n"); printf(" The list %s palindrome.n",result ? "is" : "is not"); result = isPalindrome_rec(&test); printf("According to the recursive method:n"); printf(" The list %s palindrome.n",result ? "is" : "is not"); free_list(test.next); return 0; } |
Is “bool” a C++ syntax? It seems your code is C/C++ mixed.
My code is completely pure C. ‘bool’ is both a C syntax and a C++ syntax. In the new C standard, such as C99, ‘bool’ is part of the language (http://pubs.opengroup.org/onlinepubs/007904875/basedefs/stdbool.h.html).