c - 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

要检查循环链表，只需循环链表并为每次迭代检查以下内容：

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

Answer 2

Tortoise and Hare 算法将适用于您的目的。

在每次迭代中，兔子将通过两个节点，而乌龟只移动一个。野兔会多次访问每个节点和其中一些节点，但是如果将野兔的节点访问总数相加除以 2，则结果不会大于列表的长度。乌龟也有可能会访问每个节点，但它不会访问同一个节点两次。

算法是 O(n)

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

Answer 3

所以你可以在 50 次迭代中完成它，只需一点 hack。保留另一个*head2指向 的 head( ) head->link。这仍然会占用恒定的空间。将其与 if 条件中的当前节点以及原始头部进行比较。见下面的代码——

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 4

使用单个链接列表，您必须遍历整个链接列表。这也适用于循环链接列表。否则为什么人们会做出这样的 ADT？

您可以使用双链表检查链表循环与否。您可以在恒定时间内检查它。