单链表是否有环及环入口点

参考与原理：https://www.jianshu.com/p/ef71e04241e4
https://blog.csdn.net/danny_idea/article/details/89504629
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 typedef struct node pnode;
  5 struct node
  6 {
  7     int info;
  8     pnode *next;
  9 };
 10 
 11 void create(pnode **head)   //创建链表
 12 {
 13     (*head) = (pnode *)malloc(sizeof(pnode));
 14     (*head)->info = 0;  //创建头节点，记录链表节点数
 15     (*head)->next = nullptr;
 16 }
 17 
 18 void add(pnode *head, int val)  //尾插法给链表添加节点
 19 {
 20     head->info++;
 21 
 22     while (head->next != nullptr)
 23         head = head->next;
 24 
 25     pnode *temp = (pnode *)malloc(sizeof(pnode));
 26     temp->info = val;
 27     temp->next = nullptr;
 28     head->next = temp;
 29 }
 30 
 31 void show(pnode *head)  //打印链表
 32 {
 33     printf("[%d] ", head->info);
 34     head = head->next;
 35 
 36     while (head != nullptr)
 37     {
 38         printf("%d ", head->info);
 39         head = head->next;
 40     }
 41 }
 42 
 43 void makeloop(pnode *head, int val)     //给链表建环，val为环入口，下标从1开始
 44 {
 45     pnode *temp = head;
 46 
 47     while (val--)
 48         temp = temp->next;
 49 
 50     while (head->next != nullptr)
 51         head = head->next;
 52 
 53     head->next = temp;
 54 }
 55 
 56 void judgeloop(pnode *head) //判断链表是否有环
 57 {
 58     pnode *fast, *slow;
 59 
 60     fast = slow = head;
 61 
 62     do
 63     {
 64         fast = fast->next;
 65         if (fast != nullptr)    //这里要记得判断一次是否为空
 66             fast = fast->next;
 67 
 68         slow = slow->next;
 69     } while (fast!=nullptr && fast!=slow);
 70 
 71     if (fast == slow)
 72         printf("有环
");
 73 
 74     else
 75         printf("无环
");
 76 }
 77 
 78 void findEntrance(pnode *head)  //找链表环入口，下标从1开始
 79 {
 80     pnode *fast, *slow;
 81 
 82     fast = slow = head;
 83 
 84     do
 85     {
 86         fast = fast->next;
 87         if (fast != nullptr)
 88             fast = fast->next;
 89 
 90         slow = slow->next;
 91     } while (fast!=nullptr && fast!=slow);  //先使两指针相遇
 92 
 93     slow = head;
 94     int ind = 0;    //记录下标
 95 
 96     while (fast != slow)
 97     {
 98         slow = slow->next;
 99         fast = fast->next;
100         ind++;
101     }
102 
103     printf("入口节点下标：%d
", ind);
104 }
105 
106 int main()
107 {
108     pnode *head;
109 
110     create(&head);
111     add(head, 1);
112     add(head, 2);
113     add(head, 3);
114     add(head, 4);
115     add(head, 5);
116     add(head, 6);
117     show(head);
118     judgeloop(head);
119     makeloop(head, 3);
120     judgeloop(head);
121     findEntrance(head);
122 
123     return 0;
124 }