前言
我们在解决环形链表问题之前呢，先做一道简单题做做铺垫；
环形链表的方法很简单，但是想要弄懂其中的原理，就不得不花费一番力气！！！😊😊😊接下咱就和大家一起来探讨一下这个问题！！！；
相交链表
题目描述：
➡️ 挑战链接 ⬅️
分析：
首先我们最容易想到的就是暴力破解，将一个链表的节点地址与另一个链表的每一个节点的地址进行比较，看看是否存在相同节点的情况，如果存在，则说明，两个链表存在相交；如果两个链表都遍历完了都没找到相同地址的节点，则说明两个链表无相交的情况出现；
时间复杂度：O（N^2）
空间复杂度：O(1)
代码实现：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA;
struct ListNode *curB=headB;
for(curA=headA;curA;curA=curA->next)
{
for(curB=headB;curB;curB=curB->next)
if(curB==curA)
return curA;
}
return NULL;
}
我们可以看到时间效率并不高，该算法还可以进一步改进；
方法2：
假设题目给定的两个链表一样长的话，我们就可以比较curA和curB的地址值，看看所指节点的地址是否一样，如果不一样则curA与curB同时向后走；
如果最后走到NULL都没找到的话，那么就说明两个链表不存在相交；相反如果存在curA等于curB则说明存在相交，直接返回curA或curB；
但是：
现在前提是我们不能保证两个链表是否一样长，则就需要我们去统计两个链表的长度了，然后让长链表先走长度差的绝对值步；这是就能保住curA和curB是一样长的了，就可以利用上面的思路了：
画图：
size_t CountList(struct ListNode*head)
{
struct ListNode*cur=head;
int len=0;
while(cur)
{
len++;
cur=cur->next;
}
return len;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *cur1=headA;
struct ListNode *cur2=headB;
int len1=CountList(headA);
int len2=CountList(headB);
int k=0;
if(len2>len1)
{
k=len2-len1;
while(k--)
cur2=cur2->next;
}
else
{
k=len1-len2;
while(k--)
cur1=cur1->next;
}
while(cur2)
{
if(cur1!=cur2)
{
cur1=cur1->next;
cur2=cur2->next;
}
else
return cur1;
}
return NULL;
}
时间复杂度：O（N）；
空间复杂度：O（1）；
代码改良版：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA;
struct ListNode *curB=headB;
int lenA=0;
int lenB=0;
//1、先判断一下每个链表的最后一个节点是否相等，如果最后一个节点都不想等，说明两个链表一定没有相交；反之，则一定相交了；
while(curA->next)
{
curA=curA->next;
lenA++;
}
while(curB->next)
{
curB=curB->next;
lenB++;
}
if(curB!=curA)//两链表最后一节点比较
return NULL;
//以上没有相交的链表都没拦截于此
//接下来就是处理一定相交的链表，还是上面代码的思路；
struct ListNode *LongList=headA;
struct ListNode *ShortList=headB;
if(lenB>lenA)
{
LongList=headB;
ShortList=headA;
}
int gap=abs(lenB-lenA);//两链表的节点数目差值
//先让长链表先走gap步
while(gap--)
{
LongList=LongList->next;
}
//两个链表保持一致长了
while(LongList)
{
if(LongList==ShortList)
break;
LongList=LongList->next;
ShortList=ShortList->next;
}
return ShortList;
}
环形链表Ⅰ
前面铺垫做完了，我们再来慢慢进入正题：
题目描述：
➡️ 挑战链接 ⬅️
分析：
首先解决这道题目的方法就是快慢指针，fast指针每次走2步，slow指针每次走1步；
如果有环的话，fast指针一定会等于slow指针（why？我们下文解释）；
如果没环的话，fast最后一定是等于NULL或者fast->next==NULL；
偶数节点，无环情况，结束条件；
奇数节点，无环情况，结束条件
时间复杂度：O（N）
空间复杂度：O（1）
代码实现：
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)//说明带环
return true;
}
return false;
}
代码和思路就是这么简洁
下面我们来解释一下：为什么快指针每次走两步，慢指针走一步可以？快指针可不可以每次走3步？
假设链表带环
首先我们清楚一定是快指针先进入圆环，对吧！
其次呢，当我slow指针刚好在圆环进入点的时候，fast指针也存在与圆环中的某个位置，如图：
同时呢，我们假设fast和slow指针的相对步长呢为N步（顺时针方向的步长），现在我们fast指针是每次走两步，slow指针是每次走一步，那么我们就走呗：
同时我们可以知道fast和slow指针没变换一次，他们之间的距离就会减少1步；
why？
我们可以这样理解，假设只有fast动，那么fast和slow之间的距离是不是就是N-2；
但是现在加上slow动的距离，fast和slow之间的距离是不是又被拉大了，变为N-2+1，即N-1；
后面以此类推……
那么fast与slow之间的距离变化就是：
N
N-1
N-2
N-3
……
0//
fast和slow之间距离最后会减小为0；
当N0了就说明fast与slow并肩同行了，也就是说fastslow了；
这样解释了，为什么fast每次走2步，slow每次走1步，最会一定会在环里面并肩；
那么我们再来看看，fast每次走3步，slow每次走1步行不行嘞？
还是刚才的思路，fast与slow的初始距离为N：
那么下一次的距离就变为了N-2；
假设只有fast动，距离就是N-3，加上slow移动距离，使得slow与fast之间距离变大，N-3+1，即N-2；
后面依次类推……
N的变化规律：
N
N-2
N-4
……
假设N是偶数的话，那么N最后一定会减为0，那么fast一定能与slow并肩，也就一定能有fast==slow；
假设N是奇数的话，那么N最后一定会为-1，这个-1代表什么意思？
就是说fast与slow擦肩而过，fast刚好领先slow一步，这时我们设圆环周长为C，
那么fast和slow之间的距离（fast到slow，顺时针）就为C-1；
这不有回到上一层？
令T=C-1
T的变化：
T
T-2
T-4
……
假设T为偶数的话，那么slow与fast指针一定能并肩；
假设T为奇数的话，那么fast与slow永远不可能并肩了；
why？
T都为奇数了，那么是不是最后又会回到T=-1的时候？是不是又回到了上图表示的情形，fast与slow之间的距离又是T（C-1）然后就这样不断循环，所以fast永远不可能并肩；
这也就是我们为什么会让fast走2步，slow走1步的原因；（当然只要fast与slow之间的速度差等于1，理论上来说都是可以并肩的）
————————————————————————————————————————————————
同时，如果我们悬着fast每次走2步，slow每次走一步的情况的话，slow和fast最多在一圈内完成并肩；
我们再来证明这个理论：
好了，现在我们知道了这些原理和解释，我们来给环形链表加点难度；
环形链表Ⅱ
题目描述：
➡️挑战链接⬅️
分析:
通过上面的题我们知道了如何判断一个链表是不是环形链表,那么我们的对于上面的码,我们可以稍加处理:
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)//说明带环
{
//核心部分
}
}
return NULL;//链表无环
}
这时问题就变为了,如何计算带环链表的进环入口,
首先我先说结论;
我们通过上文的证明,我们知道如果fast每次走2步,slow每次走一步,一定会在环内相遇,
那么我们吧相遇点记为meet,然后将链表头节点记为plist,然后让plist和meet每次都走1步的速度往后走,最后一定会存在meet等于plist的情况,那么那个相等的点就是入口点!!;
代码实现:
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)//说明带环
{
//核心部分
struct ListNode *meet=slow;
struct ListNode *plist=head;
while(plist!=meet)
{
meet=meet->next;
plist=plist->next;
}
return plist;
}
}
return NULL;//链表无环
}
我们现在来解释一下,为什么meet与plist为什么一定会相遇,并且一定相遇与入口点:
当然前面我们证明了,slow与fast一定在一圈以内完成并肩,因此slow的距离是L+N;
如果上面寻找入口节点的方法不明白,还有个更简单的办法,就是将meet位置节点剪掉,同时将slow->next置空,那么环形链表是不是就变为了相交链表,而入口点不就是第一个相交点嘛:
于是我们当一把CV工程师:
代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA;
struct ListNode *curB=headB;
int lenA=0;
int lenB=0;
while(curA->next)
{
curA=curA->next;
lenA++;
}
while(curB->next)
{
curB=curB->next;
lenB++;
}
if(curB!=curA)
return NULL;
struct ListNode *LongList=headA;
struct ListNode *ShortList=headB;
if(lenB>lenA)
{
LongList=headB;
ShortList=headA;
}
int gap=abs(lenB-lenA);
while(gap--)
{
LongList=LongList->next;
}
while(LongList)
{
if(LongList==ShortList)
break;
LongList=LongList->next;
ShortList=ShortList->next;
}
return ShortList;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)//说明带环
{
//核心部分
struct ListNode *plist=head;
struct ListNode *meet=slow->next;
slow->next=NULL;
return getIntersectionNode(plist,meet);
}
}
return NULL;//链表无环
}
时间复杂度:O(N)
空间复杂度:O(1)
