C++ Interview Questions and Answers

 

Tell how to check whether a linked list is circular.

Create two pointers, each set to the start of the list. Update each as follows:



while (pointer1) {



pointer1 = pointer1->next;



pointer2 = pointer2->next; if (pointer2) pointer2=pointer2->next;



if (pointer1 == pointer2) {



print ("circularn");



}



}





OK, why does this work?



If a list is circular, at some point pointer2 will wrap around and be either at
the item just before pointer1, or the item before that. Either way, it’s either
1 or 2 jumps until they meet.

Posted by:Richards