目录
1.环形链表Ⅰ
编辑
思路 ：
思路拓展
问题一：
问题二：
总结：
问题三：
证明总结第三点
总结：
2. 环形链表Ⅱ
思路一
思路二
3.相交链表
思路：
1.环形链表Ⅰ
141. 环形链表 - 力扣（LeetCode）
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。
思路 ：
我们考虑环状时，如果是简单的循环next来判定，只会进入死循环；
需要引入新思维，判断是否带环，可以想象操场追赶问题，两个人在操场跑；让一个人先进场跑，再让另外一名选手进场，如果环足够大，如何让后入场的选手追赶上前面的；答案是，后来者加快速度。
而在这道题中，我们用快慢指针概念，一个指针走两步，一个走一步，进入环后，快指针一定会和慢指针相遇
为什么一定会相遇呢？
距离为N，每次快指针走两步，慢指针走一步相当于距离每次减少1；
如此距离缩短，肯定会相遇，而当快慢指针相遇的时候，就是证明该链表带环；
而如果不带环，快指针将链表走完后，表明退出了循环即可；
bool hasCycle(struct ListNode *head) {
//快慢指针
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}思路拓展
上面说到，距离缩小1一定会追上，那如果距离一次缩小2呢，是不是更快的会相遇呢
如果一次距离缩小n，是不是更快呢；如此延申，我们可以发现有三个拓展
1. slow一次走一步，fast一次走两步，一定会相遇吗
2.slow一次走一步，fast一次走三步，一定会相遇吗
3.slow一次走n步，fast一次走m步，一定会相遇吗 （m>n>1）
问题一：
距离缩小为1的话，一定会遇上，我们上面证明了
问题二：
当slow进环时，fast和它的距离为N，一次减少2。分为两种情况
1.当N是偶数时：
2.当N是奇数时：
所以，我们可以发现，当N是偶数时，依然可以追上
当N是奇数是，得到下一轮：
这时候要看 C-1是奇偶数
如果c-1是偶数：在下一轮就会追上，
如果c-是奇数：则会开始无限循环下去，一直追击不上；
总结：
1.如果N是偶数，第一轮内就会追上；
2.如果N是奇数，C是奇数，第一轮会错过，下一轮会追击（C是奇数，C-1就会是偶数）；
3.如果N是奇数，C是偶数，就永远追不上；
问题三：
这个类似问题二，每次距离缩小是m-n(>=1);
如果N%(m-n) == 0 说明一圈就可以追上；
如果是-1，则是C-1，-2就是C-2；
如果这个数是m-n的倍数，如果不是倍数，则可能存在死循环
证明总结第三点
写到这里时，问题二的 总结第三点，是否真的成立呢？
3.如果N是奇数，C是偶数，就永远追不上；
此刻，slow走了L的路程，fast走了 L + nC - N；
在这时，可以推论出公式
推论出来的这个公式：
2L：一定是偶数，
n*C:总结第三点假设这里是偶数；
N：如果要满足此公式，N就不可能会奇数，
所以， 3.如果N是奇数，C是偶数，就永远追不上；
这句话的条件不成立
总结：
1.如果N是偶数，第一轮内就会追上；
2.如果N是奇数，C是奇数，第一轮会错过，下一轮会追击（C是奇数，C-1就会是偶数）；
只存在这两种
bool hasCycle(struct ListNode *head) {
//快慢指针
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}
在这种情况下，该情况其实还可以推论出另一个公式结论 。这就是第二题
2. 环形链表Ⅱ
142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路一
我们依旧用上一道题的画图思路来解决，
第一步先判断是否存在环，
第二部找到入口点；
用快慢指针方法，slow走一步，fast走两步
struct ListNode *detectCycle(struct ListNode *head) {
//快慢指针
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow) //相遇了
{
struct ListNode* meet = slow;
while(head != meet) //起点和相遇点
{
head = head->next;
meet = meet->next;
}
//找到入口点了
return meet;
}
}
return false;
}思路二
这道题还有另外一种解法，就是在相遇点meet这里，将下一个节设为newnode，再将meet->next置NULL，这样就将带环链表问题转换成 相交链表问题
而这种解法自然有相交链表的题；
但是这种解法比较复杂，建议用思路一的
3.相交链表
160. 相交链表 - 力扣（LeetCode）
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路：
题目两种情况，存在相交和不相交，
相交还有前后长短问题；
1.先判断是否有相交点；如果相交，尾节点一定相同；
2.计算两条链表的长度，让长链表先走差距步，这样可以让两条链表处于相同head；
3.再让两条链接一起走，直到遇到相同点；
返回相遇点或者是结束链表遍历返回NULL；
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA = headA,*curB = headB;
//计算两条链表长度
int lenA = 0;
int lenB = 0;
while(curA)
{
lenA++;
curA = curA->next;
}
while(curB)
{
lenB++;
curB = curB->next;
}
//算出长度差
int n = abs(lenA-lenB);
//假设lenA 长于lenB
struct ListNode* longlist = headA,*shortlist = headB;
if(lenB>lenA) //假设不成立，交换
{
longlist = headB;
shortlist = headA;
}
//长的先走差值
while(n--)
{
longlist = longlist->next;
}
//判断是否相等
while(longlist != shortlist)
{
longlist = longlist->next;
shortlist = shortlist->next;
}
//到这里要么相等，要么链表不相交，已经走完了是NULL
return longlist;
}
