前言🌸
各位读者们好，本期我们来填填之前留下的坑，继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是，我们今天的题目主要是于环形链表有关，下面让我们一起看看吧。
💻本期的题目有： 环形链表、 环形链表II、 求环形链表环长
环形链表💍
a.题目
b.题解分析
第一种方法，我们可以遍历链表，使用哈希表来保存已经经过的结点。每次经过一个结点时，通过哈希表判断结点是否被访问过，如果有，则说明存在环；如果没有则继续访问下一结点，以此循环直到遍历完整个链表。这样的时间复杂度为O(N)，空间复杂度为O（N），不满足题目的进阶解法。
第二种方法，我们可以使用上期学习的快慢指针法。定义步长为2的快指针和步长为1的慢指针遍历链表。我们假设链表如果存在环，则快慢指针在某一时刻一定会在环内相遇；而如果不存在环，由于快指针速度比慢指针快，因此它们永远无法相遇。动态效果如下：
我们可以看到如果链表存在环时， 当慢指针进入环中后，快指针就会开始绕环追逐慢指针。我们假设此时快慢指针距离为n，由于 v(快)-v(慢)=1，则每次行动快慢指针的距离就会缩短1， 行动n次后快慢指针一定就会相遇。因此我们可以通过判断是否相遇来判断是否有环。
c.AC代码
struct ListNode
{
int val;
struct ListNode* next;
};
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 (fast == slow)
{
return true; //相遇
}
}
return false; //没有相遇、没有结点、只有一个结点且非循环，不存在环
}d.拓展思考
通过以上例子，我们知道 速度差为1的 快慢指针可以用来判断链表是否存在环。那么， 速度差为2的是不是也可以用来判断呢？速度差为3的呢？为n的呢？
我们来分析一下：当快慢指针的速度差为2时，假设慢指针进入环时快指针与其距离为n，环的总长为m，如下：
由于它们的速度差为2，则每次行动后n=n-2。我们很容易发现，如果n为偶数时，当行动
次后快慢指针就会相遇；但是当n为奇数时，最后快慢指针就会错过，进入下一轮追赶中。而在第二轮追赶开始时，快慢指针距离为m-1，假如m-1又是奇数，则本轮又会错过进而进入第三轮追逐。然后第三轮开始时依旧相距m-1，又会错过，以此反复......，最后永远不会相遇（史上最遥远的距离，无非就是我在你身旁，你却不理不睬😭）因此，使用速度差为2的快慢指针，不能保证是否可以判断出某个链表是否存在环，速度差为3，为n的同理。
环形链表 II✈
a.题目
b.题解分析
我们同样可以在上一题的基础上使用快慢指针来求解。
我们假设链表头到环入口的长度为S，环的长度为C。当慢指针走到环入口，此时快指针的位置和慢指针的位置关系如下：
我们假设此时快慢指针的距离为L，这里可能有读者有疑问：快指针是慢指针速度的2倍，那L的大小不应该是S吗？实际上，当slow到达环入口时，fast可能已经绕环n圈了，所以fast实际走过的长度共为S+nC+L(
)。由此我们可以得出S+nC+L=2S，即L=S-nC。在这之后，快指针开始追逐慢指针，我们假设在如下位置相遇：
假设共进行了D次追逐才追上了慢指针，由快指针比慢指针快一倍可以得出以下关系：
因此，相遇点到快指针最初位置的距离为S-nC-D，由此可以得出相遇点到环结点的距离为S-nC-D+D=S-nC,如下：
至此，我们发现链表头到环入口的距离S与相遇点到环入口的距离S-nC相差n个环的长度。
由此我们算法的思路是：
起初快指针速度为2，慢指针速度为1，如果快慢指针没有相遇，则返回NULL代表不存在环；如果相遇了，我们就让 其中一个指针重新指向链表头，并使 两个指针的速度都为1，一直前进直到它们相遇，相遇的位置一定为环的位置。这是因为从 相遇点走S步后的位置与走S-nC步后的位置一致。
c.AC代码
struct ListNode {
int val;
struct ListNode* next;
};
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 (fast == slow) //相遇，存在环
{
//两个指针找环入口
slow = head;
while (slow!=fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;//没有相遇、没有结点、只有一个结点且非循环，不存在环,返回空
} 求环形链表的环长💫
a.题目
给定一个链表的头节点 head ，返回链表环中环的长度。 如果链表无环，则返回 0。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
b.题解分析
法一：我们同样可以先使用快慢指针判断链表是否存在环，当二者第一次相遇时说明链表存在环。而当快慢指针相遇后我们再次让快慢指针进行追逐战，此时它们之间的距离为环长C，由于每次追逐它们的距离都会缩短1，因此我们可以定义一个计数器count记录第二次相遇时所追逐的次数即为链表的环长。具体过程如下：
c.AC代码
struct ListNode {
int val;
struct ListNode* next;
};
int CycleLength(struct ListNode* head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next) //当到达或即将到达链表尾时退出循环
{
//快慢指针移动
fast = fast->next->next;
slow = slow->next;
if (fast == slow) //第一次相遇，存在环
{
//统计第二次相遇所追逐的次数
int count = 0;
do
{
fast = fast->next->next;
slow = slow->next;
count++;
} while (fast != slow);
//相遇了，返回追逐次数即为环长
return count;
}
}
//不存在环，返回0
return 0;
}以上，就是本期的全部内容啦🌸文章来源：https://www.toymoban.com/news/detail-822653.html
制作不易，能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-822653.html
到了这里，关于【刷题篇】链表（下）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
