c - 减少C中链表遍历时的迭代次数

Question

我有一个有 100 个节点的单链表。我是否需要检查这个链表循环？

可以通过遍历链表来实现，需要检查最后一个节点的链接字段是否等于head。

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

此方法最多需要 100 次迭代。我想将其减少一半，我的意思是通过 50 次迭代我需要实现这一目标。

可以这样做吗？如果是，我们该如何做到这一点？

Answer 1

所以你可以通过一些小技巧在 50 次迭代中完成它。保留另一个指向 head->link 的 head(*head2)。这仍然需要恒定的空间。将其与 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++;
}