【刷题篇】链表（下）

╰半夏微凉° 2024-04-25 20:03 83阅读 0赞

![258dbdb062a27027ce96dcc8d158f35f.gif][]

1.  ### 前言? ###

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

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

1.  ### [环形链表][Link 1]? ###

#### a.题目 ####

![f5d0b03496fa4db69975ceaedc3f150a.png][]

#### b.题解分析 ####

第一种方法，我们可以遍历链表，使用**哈希表**来保存已经经过的结点。每次经过一个结点时，通过哈希表判断结点是否被访问过，如果有，则说明存在环；如果没有则继续访问下一结点，以此循环直到遍历完整个链表。这样的时间复杂度为O(N)，空间复杂度为O（N），不满足题目的进阶解法。

第二种方法，我们可以使用上期学习的**快慢指针法**。定义步长为2的快指针和步长为1的慢指针遍历链表。我们假设链表如果存在环，则快慢指针在某一时刻一定会在环内相遇；而如果不存在环，由于快指针速度比慢指针快，因此它们永远无法相遇。动态效果如下：

![75f41630aca50b474f0520666427d256.gif][]

> 我们可以看到如果链表存在环时， 当慢指针进入环中后，快指针就会开始绕环追逐慢指针。我们假设此时快慢指针距离为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，如下：

![63ff182153e84f8b84448e022cd7c229.png][]

由于它们的速度差为2，则每次行动后n=n-2。我们很容易发现，如果n为偶数时，当行动![0d18cce08c964d4a8473e0327306c9c7.png][]次后快慢指针就会相遇；但是当n为奇数时，最后快慢指针就会错过，进入下一轮追赶中。而在第二轮追赶开始时，快慢指针距离为m-1，假如m-1又是奇数，则本轮又会错过进而进入第三轮追逐。然后第三轮开始时依旧相距m-1，又会错过，以此反复......，最后永远不会相遇（史上最遥远的距离，无非就是我在你身旁，你却不理不睬?）因此，使用速度差为2的快慢指针，不能保证是否可以判断出某个链表是否存在环，速度差为3，为n的同理。

1.  ### [环形链表 II][II]✈ ###

#### a.题目 ####

![0ec689cea7704d49943fe9be7649a613.png][]

#### b.题解分析 ####

我们同样可以在上一题的基础上使用**快慢指针**来求解。

我们假设链表头到环入口的长度为S，环的长度为C。当慢指针走到环入口，此时快指针的位置和慢指针的位置关系如下：

![1724caa0b9ba4e6291f278386bf2193a.png][]

我们假设此时快慢指针的距离为L，这里可能有读者有疑问：快指针是慢指针速度的2倍，那L的大小不应该是S吗？实际上，当slow到达环入口时，fast可能已经绕环n圈了，所以**fast实际走过的长度共为S+nC+L(![8f2f10be0e2041399351d108addb0b85.png][])。**由此我们可以得出S+nC+L=2S，即L=S-nC。在这之后，快指针开始追逐慢指针，我们假设在如下位置相遇：

![6f87a010489e42c6ac6245ae23ac655c.png][]

假设共进行了D次追逐才追上了慢指针，由快指针比慢指针快一倍可以得出以下关系：

![d6d67146661f48159b81b42e298c1500.png][]

因此，相遇点到快指针最初位置的距离为S-nC-D，由此可以得出相遇点到环结点的距离为S-nC-D+D=S-nC,如下：

![30d1e4403f944909aa0979f2ed635b30.png][]

![e16e8c8fab544d819dbbffb99a80143d.png][]

至此，我们发现链表头到环入口的距离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;//没有相遇、没有结点、只有一个结点且非循环，不存在环,返回空
    
    }

1.  ### 求环形链表的环长? ###

#### a.题目 ####

> 给定一个链表的头节点 head ，返回链表环中环的长度。 如果链表无环，则返回 0。  
> 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

#### b.题解分析 ####

**法一：**我们同样可以先使用**快慢指针**判断链表是否存在环，当二者第一次相遇时说明链表存在环。而当快慢指针相遇后我们再次让快慢指针进行追逐战，此时它们之间的距离为环长C，由于每次追逐它们的距离都会缩短1，因此我们可以定义一个计数器count记录第二次相遇时所追逐的次数即为链表的环长。具体过程如下：

![afbcea6af5aeb7b85655bc65088700f6.gif][]

#### 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;
    
    }

--------------------

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

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

[258dbdb062a27027ce96dcc8d158f35f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/1cef24514a1e42aab0205f3bc4f6599d.gif
[Link 1]: https://leetcode.cn/problems/linked-list-cycle/
[f5d0b03496fa4db69975ceaedc3f150a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f800a51251394ab2a33d2b0e68a16aa2.png
[75f41630aca50b474f0520666427d256.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/569412f088844fb391b458fe94b120d8.gif
[63ff182153e84f8b84448e022cd7c229.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/50fafc8bc06b48299902005821a2bd19.png
[0d18cce08c964d4a8473e0327306c9c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/cd50bdcd787a4feca88983d09d75fe2c.png
[II]: https://leetcode.cn/problems/linked-list-cycle-ii/
[0ec689cea7704d49943fe9be7649a613.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e0537d3524784849beeec420aee9a29a.png
[1724caa0b9ba4e6291f278386bf2193a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e84279bfbf884f4d92fe6871f2cd2839.png
[8f2f10be0e2041399351d108addb0b85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ea1c76e23eb74fc49aa837977adbf7d6.png
[6f87a010489e42c6ac6245ae23ac655c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/388bfc3a57c54e0280543500b7cf53d4.png
[d6d67146661f48159b81b42e298c1500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ad465b254a2443d79d089cf6555e855d.png
[30d1e4403f944909aa0979f2ed635b30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/b72e0564595449fdb02e59cbebdef674.png
[e16e8c8fab544d819dbbffb99a80143d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/18ef02eae2b34635b1315a3a57607d84.png
[afbcea6af5aeb7b85655bc65088700f6.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/a814ea2f70284bccb6e4efab8a21409a.gif