Reduce the number of iteration when traversing in linked list in C

Question

I have a singly linked list which has 100 node. I need to check this linked list circular or not?

It can be achieved by traversing list and need to check last node link field equal to head.

struct node *temp1, *temp2;
while(i != 100) {
  temp2 = temp1->link;
  if(temp2==head) {
    printf("circular");
    break;
  else
    temp1=temp1->link;
      i++;
  }

This method will take maximum of 100 iteration. I want to reduce this to half, i mean by 50 iteration i need to achieve this.

Is it possible to do this? If yes, how we can do this?

Answer 1

So you can do it in 50 iterations with a little hack. Keep another head(*head2) which points to head->link. This will still take constant space. Compare it with the current node in the if condition along with the original head. See the code below--

struct node *head, *head2, *temp;
temp = head; //assuming head points to start of the list
head2 = head->link;
while(i != 50) {
  temp = temp->link->link;
  if(temp==head || temp==head2) {
    printf("circular");
    break;
  }
  i++;
}