检测单链表中是否有环（C语言）

检测单链表中是否有环（C语言）

• 方法：双指针法

• 思路:

  使用两个指针，两个初始时都指向链表的头结点，然后one指针一次加一，另一个two指针一次加二。

  在链表有环时，two指针与one指针相等就说明有环。

  当one指针到达环的起始位置时，two指针已经在环中，此时，由于是环的结构，相当于two指针在追one指针， 由于每two指针每次比one指针快一， 所以，one只需再走两个指针之间的距离的次数，two指针就可以追上one指针。距离小于环的长度。
  最终的循环次数小于等于n，最坏情况为n次。所以，时间复杂度是O（n）。

• 图解

  • 当one指针进入环的初始点时，two指针可能已经在环循环多次，此时正好在图中的位置。
  • 此时，就可以看成是two指针在追one指针，由于two每次都比比one快1，所以，在图中1的位置可以判断，再经过5次移动，two和one就会处于同一个位置。
  • 演示结果与预期一致。
  链表中环检测算法图.png

• 代码

  #include <stdio.h>
  #include <malloc.h>
  
  //构造结构体
  typedef struct list
  {
    int data;
    struct list *next;
  }*List,LNode;
  
  //函数声明
  List init_list(List head);
  int Detection(List head);
  
  void main()
  {
      List head;
      head = (LNode*)malloc(sizeof(LNode));
      head = init_list(head);
      if(Detection(head))
          printf("单链表中有环!\n");
      else
          printf("单链表中无环!\n");   
  }
  
  
  //链表初始化函数
  List init_list(List head)
  {
    int i = 1;
    List p = head;
    while(i <= 8)
    {
        List s;
        s = (LNode*)malloc(sizeof(LNode));
        s->data = i;
        s->next = NULL;
        p->next = s;
        p = p->next;
        i++;
    }
      p->next = head->next->next;
    return head->next;
  }
  
  //双指针检测单链表中是否有环
  int Detection(List head)
  {
      //0为无环，1为有环
      List one = head;
      if(head->next == NULL)
          return 0;
      List two = head->next->next;
      while(two != NULL)
      {
          one = one->next;
          two = two->next->next;
          if(one == two)
              return 1;
      }
      return 0;
  }