There is a follow up question: how to determine whether two linked lists, to say list1 and list2, intersect each other. Two solutions are available for this problem.
On one hand, we could link the end of list1 to the beginning of list2. Then this question turns to be the same as the original problem.
On the other hand, we can travel these two lists, get their length, and get their last nodes. If the last nodes are actually one node, these two lists intersect. If they intersect, we move the longer list, to safely assume it is list1, with len(list1)-len(list2) steps. Then iteratively in each round, two lists move one step, and compare their current nodes. The first same node is the intersection point of these two lists. (Here the same means they are essentially one node.)
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 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-05-10 09:57 # Filename: 2.6.c # Description: find the entry point of the loop in a circular list =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> // for the singly linked list struct list{ char value; bool last_node; // Only for easily print and free the list // in this demo. struct list *next; }; bool build_list(struct list *head, char *content); void free_list(struct list *head); void print_list(struct list *head); struct list *find_loop_entry(struct list *head); 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 != ''){ if( strchr(content,*item) < item ){ // Loop closed current = head->next; while(true){ // Determune the entry point of the loop if(current->value == *item){ break; } current = current->next; } previous->last_node = true; previous->next = current; break; } else{ 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; current->last_node = false; 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; if( current->last_node ){ free(current); break; } 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); if(temp->last_node){ if( temp->next != NULL ){ printf(" -> previous node %c",temp->next->value); } break; } } return; } struct list *find_loop_entry(struct list *head){ // Find out the entry point of the list's loop, if // there is. // Return value: NULL if there is no loop; // pointer to the entry node of the loop, if there is. // Take the list as two part: outside the loop and inside // the loop. And let m be the length of the first part of // list, and n be the length of the second part. struct list *faster=head, *slower=head; // The following loop can be seperated into two steps: // // 1st step: the slower runs m nodes, and the faster runs // 2*m nodes. As a result, within the *loop*, // the slower is at 0 position, and faster is at // m%n position. // // In the loop, the faster is m%n steps ahead of slower. In // each round, faster takes two steps, and slower takes one // step. So faster will catch up with the slower with one // step per round. The total distance from faster to slower // is (n-m%n)%n=(-m)%n. Thus it will take (-m)%n rounds for // faster to catch up with slower. // // 2nd step: the slower runs (-m)%n nodes, and the faster runs // (2*((-m)%n))%n = (-2m)%n. Consequently, the // position of the faster is ( m%n + (-2m)%n )%n // = (-m)%n // while(faster != NULL && faster->next != NULL){ faster = faster->next->next; slower = slower->next; if(faster == slower){ break; } } // Check whether there is a loop if(faster == NULL || faster->next == NULL){ // No loop exists. return NULL; } // The slower points to the begin again. And both faster // and slower run one node per round. // // The slower runs m nodes to the 0 position of the loop, // that is the entry point of the loop. // The faster also runs m additional nodes. Then its position // in the loop would be (m + (-m)%n)%n = 0. // So at the entry point, the slower meets with the faster. // slower = head; while(faster != slower){ faster = faster->next; slower = slower->next; } return slower; } int main(int argc, char *argv[]){ struct list test = {.value = '', .next = NULL}; struct list *result = NULL; // 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->previous c node (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 = find_loop_entry(&test); if(result == NULL){ printf("The list has no loop.n"); } else{ printf("The entry point of the loop is: %cn",result->value); } free_list(test.next); return 0; } |