The description of this question is not quite clear. What does “given only access to that node” exactly mean? If we cannot read any other node, it is impossible to finish the work. If we could only read the node, we should remember to free the deleted node somewhere else to avoid the memory leak. In my solution, I return the pointer to the really-deleted node inside the function, and free it outside.
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 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-20 23:46 # Filename: 2.3.c # Description: remove the middle node but not modify any other node. =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.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 *remove_middle(struct list *head){ // This function will remove the middle node, // and return the pointer to the really-removed node. struct list *former = NULL, *latter = NULL, *temp = NULL; // Check the input parameter if( head == NULL || head->next == NULL){ return NULL; } // A special case that there is only one node in the list // We need to change the head node ONLY in this case if( head->next->next == NULL ){ temp = head->next; head->next = NULL; return temp; } former = head->next; latter = head->next; // Move the formar pointer two steps per move // and the latter one step per move while( former->next != NULL && former->next->next != NULL){ former = former->next->next; latter = latter->next; } if(former->next != NULL ){ // There are even number of nodes in the list. // So there is no middle-node to remove. return NULL; } // Currently, the middle node is the "latter". temp = latter->next; latter->value = latter->next->value; latter->next = latter->next->next; return temp; } 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 = false; // Check the arguments if(argc < 2){ printf("Usage: %s word1 word2 ...n",argv[0]); return -1; } if( argc%2 != 0 ){ printf("The number of nodes in the list must be odd.n"); return -1; } // prepare the head node head = (struct list *)malloc(sizeof(struct list)); if(head == NULL){ printf("Fail to allocate memory.n"); return -2; } head->value = NULL; head->next = NULL; // Prepare the test linked list if( build_list(head, argv+1) == false){ free_list(head); printf("Fail to build the list.n"); return -3; } // Find the node and print it printf("Original list: "); print_list(head); result = remove_middle(head); if(result != NULL){ printf("Processed list: "); print_list(head); free(result); } else{ printf("Fail to find or remove the middle node.n"); } free_list(head); return 0; } |