【手撕代码1】-判断单链表是否有环+求环的长度+求入环点

核心思想：快慢指针

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 struct listnode {
 6     int val;
 7     listnode* next;
 8 };
 9 listnode* meet;
10 listnode* head;
11 //判断是否有环
12 bool panduan(listnode * head)
13 {
14     if (head == NULL)return false;
15     listnode* fast=head;
16     listnode* slow=head;
17     //因为这里fast有两个next，所以要保证fast->next也不为空
18     while (fast != NULL&&fast->next!=NULL)
19     {
20         if (fast == slow)
21         {
22             meet = fast;
23             return true;
24         }
25         fast = fast->next->next;
26         slow = slow->next;
27     }
28     return true;
29 }
30 //求环长度
31 int len()
32 {
33     listnode* p = meet;
34     int sum = 1;
35     p = p->next;
36     while (p != meet)
37     {
38         sum++;
39         p = p->next;
40     }
41     return sum;
42 }
43 //求入环点 L=kc-n
44 //只需要找到相遇节点，再让一个指针从头开始走即可
45 listnode* findnode()
46 {
47     listnode* a=meet;
48     listnode* b = head;;
49     while (a && b)
50     {
51         if (a == b)return a;
52         a = a->next;
53         b = b->next;
54     }
55     return NULL;
56 }
57 
58 int main()
59 {
60     
61     /*数据输入*/
62     panduan(head);
63     len();
64     findnode();
65     return 0;
66 }

具体详见 https://blog.csdn.net/etalien_/article/details/90272899