【刷题篇】链表（下）

1. 前言🌸

各位读者们好，本期我们来填填之前留下的坑，继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是，我们今天的题目主要是于环形链表有关，下面让我们一起看看吧。

💻本期的题目有： 环形链表、 环形链表II、 求环形链表环长

2. 环形链表💍

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的同理。

3. 环形链表 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;//没有相遇、没有结点、只有一个结点且非循环，不存在环,返回空

}    

4. 求环形链表的环长💫

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;

}

以上，就是本期的全部内容啦🌸

制作不易，能否点个赞再走呢🙏