The question is one step in the quick sort algorithm. The idea is to rearrange the list so that the smaller nodes than pivot are previous to all other nodes. More details could be found on Wikipedia. In the implements in the book, the author has to take extremely care of the NULL pointer. But in my implement, thanks to the head node, I do not have such issue. Additionally, the smaller-node list increases from head to tail, and the not-smaller-node list grows from tail to head. At the end, we can easily concatenate these two temporary lists without any more travels, which the official solution needs.
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 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-04-21 23:20 # Filename: 2.4.c # Description: arrange all the nodes, whose values are smaller than X node, before X. And all the others after X. =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <errno.h> // for the singly linked list struct list{ long int 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, *temp = NULL; 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; errno = 0; current->value = strtol( *word, &temp, 10); if( errno == ERANGE || *temp != ' '){ printf("Invalid number in the arguments.n"); return false; } 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; } bool sort(struct list *head, long int k){ // This function will re-arrange the list, such that all // nodes, smaller than X_int, will before any other node. struct list *smaller = head, *not_smaller = NULL; struct list *current = NULL, *temp = NULL; if(head == NULL){ return false; } current = head->next; while(current != NULL){ temp = current->next; if( current->value < k ){ // Append to the tail of smaller smaller->next = current; smaller = current; } else{ // Add to the head of not_smaller current->next = not_smaller; not_smaller = current; } current = temp; } // Combine two lists smaller->next = not_smaller; return true; } 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("%ld",temp->value); while(temp->next != NULL){ temp = temp->next; printf(" -> %ld",temp->value); } printf("n"); return; } int main(int argc, char *argv[]){ struct list *head = NULL; long int X_int = 0; char *strtol_res = NULL; // Check the arguments if(argc < 3){ printf("Usage: %s X-int int1 int2 ...n",argv[0]); return -1; } errno = 0; X_int = strtol( argv[1], &strtol_res, 10); if( errno == ERANGE || *strtol_res != ' '){ printf("Invalid argument for X_int: %sn",argv[1]); printf("Usage: %s X-int int1 int2 ...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 = 0; 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; } // Sort the list as: // All nodes, smaller than X_int, is before any node, // greater than or equal to X_int printf("Original list: "); print_list(head); if( !sort(head, X_int) ){ printf("Fail to sort the list by the value %ld.n",X_int); } else{ printf("Sorted list: "); print_list(head); } free_list(head); return 0; } |