|
Answer» The algorithm to determine the length of the list: - At a time, pointer A advances one node while pointer B advances two nodes.
- Starting from the head, they move until B reaches null (no loop) or A and B refer to the same node.
- Now, if A simply advances, A will run into B again. The length of the loop, let's CALL it X, may be calculated from this.
- Begin again from the head, but this time have a pointer C which has moved x nodes, followed by a pointer D behind it. Both will move one node further at a time.
- When they meet, the length of the linked list with a loop is equal to the number of nodes traversed by D PLUS x.
int calcLen( Node* head ){ struct Node *A = head, *B = head; while ( A && B && B->next ) { A = A->next; B = B->next->next; /* If slow_p and fast_p meet at some point then there is a loop */ if (A == B) { int x = 1; struct Node *t = A; while (t->next != A) { x++; t = t->next; } } } struct Node *C = head, *D = head; int y = 0; for ( int i = 0; i < x; i++ ) { C = C->next; } while( C != D ) { y++; C = C->next; D = D->next; } RETURN x+y;} Time Complexity: O(n)
Space Complexity: O(1)
|
