牛客网刷题-环形链表

你的名字 2024-04-06 10:21 68阅读 0赞

**前言：  
想要学好嵌入式，C语言与数据结构是必要熟练掌握的，而想熟练掌握一门语言，必须经过大量的练习，刷题，至少需要一两万行的代码量，才能具有一定的编程能力，至少拿到一个功能，怎么去用编程语言去实现它，从现在开始我要开启刷题之路，提高自己的编程水平，还有最重要的面试能力。  
推荐一款刷题神器**

#### 导航 ####

*  一.判断链表中是否有环
 *  二.链表中环的入口结点
 *  三.如何高效刷题

## 一.判断链表中是否有环 ##

**题目原型：**  
![在这里插入图片描述][7496009d4e5947e9ba7b7a2d2be054fa.png]  
**输入输出示例：**  
![在这里插入图片描述][a1683ed5990f4cc79e1dc619d66e6f3b.png]  
**1.题目分析：题目中让我们判断一个链表是否带环，题目所说的带环不是环形链表的意思，而是最后一个结点又会重新指向前面某个结点，形成像一个环一样。**

**2.解题思路：**  
**如果仅仅采用一个指针去遍历链表（某个结点能重复遍历到表示链表有环），这种方式一定得确定一个环内的结点，因为我们不知道链表在哪一个结点入环，所以这方法根本行不通。**

**快慢指针就能巧妙解决问题，用快慢指针去遍历链表，如果链表无环则快指针先到达终点则直接返回false，如果链表有环则快指针一定比慢指针先一步到达环内，然后快指针在环内走，直到慢指针也进入环内，此时两个指针都在环内开始走，而快指针比慢指针要快，则快指针在追上慢指针，当快指针等于慢指针，这样就说明链表内有环，但是有一点虽然我们知道因为快指针比慢指针要快所以快指针一定能追上慢指针这是毋庸置疑的，但是问题来了快指针能刚好追上慢指针嘛(快指针等于慢指针)，有没有这种情况虽然快指针追上了慢指针但是每次追上都错过了(快指针每次追上的时候都跑到慢指针的前面去了)，如果是这种情况的话程序就死循环了，所以说得分情况：快指针具体比慢指针快几步？**

*  **1.快指针fast一次走2步，慢指针slow一次走1步**  
    **先说结论：fast 一个能追上slow而且正好fast=slow**  
    **证明：**  
    **fast指针比slow指针快，fast肯定先进环，等到slow刚刚进环此时fast可能已经在环里转了几圈，也可能fast还没转到一圈。**  
    ![在这里插入图片描述][1dc2f30cccd64a08be6dbc285d98f188.png]  
    ![在这里插入图片描述][ceb280238ca24a818021be3e8b890957.png]  
    **但是没关系，不管是哪种情况当fast和slow都进环的时候，fast与slow之前一定有个距离，设这个距离为N(也可能N一开始就等于0那就更好了直接fast = slow)，让fast指针去追slow指针，因为fast每次比slow多走一步，则两个指针每走一次(fast走两步slow走一步)，他们之间的距离就会每次都减1，减到最后N一定会被减成0(则此时fast= slow)。**

![在这里插入图片描述][9242b287422d4f6d9d6be48d7fd7a7f4.png]  
![在这里插入图片描述][6862eafcc8a044e7b308e8d6ca0b5520.png]

*  **2.快指针fast一次走3步，慢指针slow一次走1步**  
    **结论：不一定fast追上slow正好fast = slow  
    证明：还是假设 fast和slow都进环的时候，fast与slow之间的距离为N，fast指针开始追逐slow，fast每一次比slow多走2步，则每次N都减2  
    第一次：N=N-2  
    第二次：N=N-4  
    第三次：N=N-6  
    …**  
    **所以当N为偶数时，N确实可以减为0(fast=slow)，如果N为奇数则最后N会被减到-1，N=-1代表fast超过slow，fast等于slow的前面一个结点。如果fast超过了slow一个结点，假设环有C个结点，当N=-1时，fast 与slow 距离N又会变成C-1。如果C-1是偶数的话，则代表fast能正好追上slow(fast=slow)，如果C-1是奇数的话，则fast与slow永远会错过，程序就会死循环。**

**所以会分成以下几种情况：**

*  **当fast和slow都进环的时候，当N为偶数，fast会刚好追上slow(fast=slow)**  
    ![在这里插入图片描述][23df1c5866ff48f08665fbc0a477d7e5.png]
 *  **当fast和slow都进环的时候，环大小为C，当N为奇数，但是C-1为偶数fast还是会刚好追上slow(fast=slow)**  
    ![在这里插入图片描述][75f169bb980a4bdfb4dd627f6b5fee6d.png]
 *  **当fast和slow都进环的时候，环大小为C，当N为奇数，而且C-1也为奇数则fast与slow永远会错过，但是经过我的推理(我取一个C-1为奇数，然后逐一增加L的长度发现N的值一直是几个偶数的循环)发现好像当C-1为奇数的时候N一定为偶数，这样一来好像一次走三步fast与slow一定能刚好相遇，但是我现在无法证明，先就这样吧，有机会在去深究一下。**

**为什么选择fast指针走两步？  
为了降低时间复杂，因为fast一次走三/四…步当slow进入环fast开始追逐slow的时候可能会错过slow。**

**代码实现：**

bool hasCycle(struct ListNode* head ) {
        
        // write code here
        struct  ListNode *slow =head,*fast=head;
         
         while(fast!=NULL && fast->next!=NULL )
         {
        
             slow=slow->next;
             fast=fast->next->next;
             if(fast == slow)
             {
        
                 return true;
             }
         }
         return false;
    
    }

![在这里插入图片描述][981d9238e60743d0a8c5c8057536e883.png]

## 二.链表中环的入口结点 ##

**题目原型：**  
![在这里插入图片描述][c189a363f0984c4597eeff3a307e7eaa.png]  
**输入输出示例：**  
![在这里插入图片描述][f9f8ec7008b44cefb5d77a72f913c129.png]  
**1.题目分析：题目意思也清晰明了，如果链表带环就返回环的入口结点，若链表不带环，则返回空。**

**2.解题思路：  
这题同样是用快慢指针，fast一次走2步，slow一次走1步。  
假设环的大小为C，环的入口到链表起点的距离为L，fast与slow在距离入口结点X处相遇。  
先说结论：一个指针从环的入口结点开始走，另外一个指针从fast与slow的相遇点(而这个指针可能会在环中转上几圈)开始走，这两个指针相遇的位置就是环的入口结点，也就是要证明L=(n-1)C+C-X**

![在这里插入图片描述][7138bf415ad74641875a208d9e2c7e54.png]  
**看完上图，解决下列3个问题这道题目迎刃而解**  
![在这里插入图片描述][429756e7879f48a69db60a6488e2034b.png]  
**第一个问题：**  
![在这里插入图片描述][460b24f9025946839719655db0967e61.png]  
**第二个问题：**  
![在这里插入图片描述][757436b27adf4339a856f7cf3373a2b0.png]  
**第三个问题：**  
![在这里插入图片描述][96600b981a3f49cdb465f506f949b875.png]

**代码实现：**

**知道思路代码就很简单了**

struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
        
        // write code here
        struct  ListNode *slow =pHead,*fast=pHead;
          
        while(fast!=NULL && fast->next!=NULL)
         {
        
             slow=slow->next;
             fast=fast->next->next;
             //找到fast与slow相遇结点
             if(fast == slow)
             {
        
               struct  ListNode *meet =slow;
                 while( pHead!= meet)
                 {
        
                    pHead=pHead->next;
                    meet=meet->next;
                 }
                 //返回环入口结点
                 return meet;
             }
         }
         return NULL;
    }

![在这里插入图片描述][804ebfbd126c4656bb7f62eceab87a40.png]

## 三.如何高效刷题 ##

如何刷题：  
**1.如果你是基础不太好，可以先按照题解，跟着手打代码，重点理解题目思路，将题目所用到的知识点，解题技巧提炼出来（锻炼代码能力，解题思路）。**![在这里插入图片描述][6680fb10768c48a89fbf9725fd9aa106.png]  
**2.当有一定的代码能力之后，但是看题还是没有思路，可以先看解题思路理解它，然后尝试用代码去实现它。(主要锻炼代码能力，进一步锻炼解题思维)**

**3.拿到一个题目自己先尝试解题，最好是能将解题思路用画图的方式体现出来，这样更能加深印象，然后用代码实现，实现之后再看看题解，或者别人的解题方法，进行对比，找到最优解题思路**  
![在这里插入图片描述][56ec37aa571740aa855ae8794eb3bccf.png]  
**最后：在解题过程中，碰到问题如下图(题目提交后通不过，报错(代码可能有bug)，尽量独立思考，可以先尝试用它的测试用例，一步一步走读代码，看看问题出现在那个地方，如果实在是没有看出来，可以将该函数拷贝到VS中进行调试代码，一定能找出来。（锻炼自己的代码调试能力）**

**总结：  
要想学好嵌入式C语言是根本，但是也离不开数据结构，尤其是链表、队列方面的知识，就接下来我要更新的freerots实时操作系统，就需要用到大量的链表和队列的知识，要想提高自己的编程水平，笔试能力和面试技巧，就得大量刷题手打代码**

[7496009d4e5947e9ba7b7a2d2be054fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/76b83fc9019647f0b92c481397721505.png
[a1683ed5990f4cc79e1dc619d66e6f3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/968d848f0ada4098af70dc75d2ca97cf.png
[1dc2f30cccd64a08be6dbc285d98f188.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2aa090efea734d109c8e0722264adaad.png
[ceb280238ca24a818021be3e8b890957.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/61bacc3e922c480fae282946ee40711f.png
[9242b287422d4f6d9d6be48d7fd7a7f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/754379d7c35845b2b8a5be8d3ec682c8.png
[6862eafcc8a044e7b308e8d6ca0b5520.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/768f885b0d8d42eb98eefff3d57988c3.png
[23df1c5866ff48f08665fbc0a477d7e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/565aac9f375c47c79f7657856b6286c3.png
[75f169bb980a4bdfb4dd627f6b5fee6d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1ab2a2c0f3ad4f67b13c5ce09c188452.png
[981d9238e60743d0a8c5c8057536e883.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f60a692357744cf1a4e05caf9f6566ae.png
[c189a363f0984c4597eeff3a307e7eaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5a71f73e898646b38a2b7d4186d7a284.png
[f9f8ec7008b44cefb5d77a72f913c129.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/adf9d05ee85646ca86e77ffb282c13f5.png
[7138bf415ad74641875a208d9e2c7e54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8b1e8f1100874dfd8b501e4aad5515c9.png
[429756e7879f48a69db60a6488e2034b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/09eebd3c83f047dba695b82a87828d8a.png
[460b24f9025946839719655db0967e61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/898d8543446b4128aee2ce12f80e6dcb.png
[757436b27adf4339a856f7cf3373a2b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/318f5015a35a401f899cfbab10da2fa6.png
[96600b981a3f49cdb465f506f949b875.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2668db436e4341b5ba61fcfc352345ee.png
[804ebfbd126c4656bb7f62eceab87a40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/9d61ee05fffc4ce3823027e2ecf1c7a4.png
[6680fb10768c48a89fbf9725fd9aa106.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2348ee7def08488c83c02eae338fedc1.png
[56ec37aa571740aa855ae8794eb3bccf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/3f7b8b4e95b54540a7cb63512ec0e55f.png