一. 判断单链表有无环
a. 错误的思路：遍历陷入死循环
1）和相交的遍历思路一样，找指向相同。
错误点
一直在死循环。
思考点：如何破环
b. 个人思路：反转链表回首结点
1）目前的经验，无非就是增删查改，反转链表，快慢指针，于是一个个靠；
2）发现，反转有环链表后，会回到首结点。
图解思路如图1:
增益点：反转破环
反转链表可以跳出环的死循环。
代码
typedef struct ListNode Node;
bool hasCycle(struct ListNode* head) {
if (head == NULL)
return false;
Node* n1 = NULL;
Node* n2 = head;
Node* n3 = NULL;
while (n2)
{
n3 = n2->next;
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
if (n1 == head && head->next != NULL) 回到首结点就是有环
return true;
return false;
}
c. 参考思路：快慢指针转为追及问题
1）环相当于初中还是高中的一道物理题：在学校操场上，小狗速度是小猫的两倍，问小狗多久能追上小猫。即快指针为慢指针速度的两倍；
2）速度为两倍的考究点为，2-1=1，保证每次只追一个结点距离，实现追及结点遍历，避免陷入奇偶死循环的局面。
增益点：思路本身和二倍速度遍历所有结点
代码
typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) {
if(head==NULL||head->next==0)
return false;
Node* fast=head;
Node* slow=head;
Node* n3=NULL;
while(fast)
{
fast=fast->next;
if(fast)
fast=fast->next;
slow=slow->next;
if(slow==fast)
return true;
}
return false;
}
二. 有环，返回入环结点地址
a. 个人思路一：继续反转链表找思路（缺陷就是无用遍历多了些）
1）发现在反转思路出环的状态会出现一个反向新环；
2）遍历反向新环得到入环结点地址。
图解思路如图2:
 {
if (head == NULL)
return NULL;
Node* n1 = NULL;
Node* n2 = head;
Node* n3 = NULL;
Node* store = NULL;
while (n2)
{
n3 = n2->next;
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
store = n1;
while (store) 没环一定到NULL，有环就一直循环直到找到n1
{
store = store->next;
if (store == n1)
return n1;
}
}
return NULL;
}
b . 个人思路二：快慢指针公式求解，没做出来
列出未知数，如图5：
其中x为入环前跳数，y为慢指针入环后跳数，z为剩余跳数。
1）慢指针跑不了一个环，则x+y可知；
2）相遇后，再次跑一圈可以得到环的结点数：z+y+1。
3）快指针跳数：x+y+nz（n未知）;
4）慢指针跳数：x+y；
5）二倍速，中点数量关系：2*（x+y）=x+y+n*(y+z+1)。
四个未知数，三个等式，求不出来。
c . 参考思路一：未知数n无所谓
看成：
C=y+z+1;环结点数
2*（x+y）=x+y+nC;
x=C-y+(n-1)C;
可以看作，C-y是跑了(n-1)C的圈后的最后一圈位置。
(n-1)C相当于是白跑了(n-1)圈，不必知道n的具体大小。即从快慢指针相遇点出发一定能和head出发相遇
增益点：无，过于具体题目具体分析了
代码
typedef struct ListNode Node;
struct ListNode * detectCycle(struct ListNode *head) {
if (head == NULL)
return NULL;
Node* slow = head;
Node* fast = head;
Node* store = NULL;
while(fast)
{
fast=fast->next;
if(fast)
fast=fast->next;
slow=slow->next;
if(slow==fast)
break;
}
if(fast!=slow)
return NULL;
store= slow;
while(head!=store)
{
head=head->next;
if(store)
store=store->next;
}
return store;
}
d . 参考思路二：我把环手动断开不就行了？还死循环？
1）快慢指针判断有无环；
2）有环，相遇点直接截断；
3）转换为两个链表求相交问题。移步至相交问题。
增益点：数学家思维
高中数学老师讲过数学家思维：
数学家知道烧水过程是把水倒进壶里，点火，烧水。
在面对一壶装满冷水的水时，
数学家会：把水倒掉--------》把水倒进壶里，点火，烧水。
正常人会：点火，烧水。
