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++;
}

Answer 2

to check for circular linked list, just loop the linked list and for every iteration check the following:

if the head == temp->next than True, it does, than it's CircularLinkedList
else if temp->next == null than False

Answer 3

Using single linklist you have to traverse the whole linklist. This also applies for circular linklist. Else why would people make such ADT?

You can use double linklist to check the linklist circular or not. And you can check it in constant time.

Answer 4

The Tortoise and Hare algorithm will work for your purposes.

On each iteration the hare will move through two nodes and the tortoise just one. The hare will visit each node and some of them multiple times, but if you add the hare's total number of node visits and divide by two, the result will not be greater than the length of the list. It is possible that the tortoise will visit each node as well, but it will not visit the same node twice.

The algorithm is O(n)

Links: http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html