【C语言手撕算法】LeetCode-142. 环形链表 II（C语言）

【C语言手撕算法】LeetCode-142. 环形链表 II（C语言）

• 一、题目介绍
• 二、题目详解
  • 1.审题
  • 2.判断是否为环形链表
    • （1）思路
    • （2）代码演示
  • 3.找到入环节点
    • （1）思路
    • （2）代码演示
• 三、考考大家
• 结语

前言：
本专栏将给大家带来一些有意思的算法题
希望对大家有所帮助
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持!!!
谢谢大家 ! ! !

一、题目介绍

本篇是小编从leetcode上挑选的一道例题
同时，还是一道难度较大的面试题
就让我们来手撕这道面试题吧

下面是题目链接：

LeetCode-142. 环形链表 II

二、题目详解

1.审题

老规矩，拿到题目先审题，题目要求返回链表开始入环的第一个节点
所以，首先我们要判断该链表是否为环形链表，如果不是，那直接返回NULL就行了
若是环形链表该想办法找出返回链表开始入环的第一个节点

下面我一步一步带大家解出此题

2.判断是否为环形链表

（1）思路

如果链表不为环形链表，遍历链表就一定会走到空指针
但是如果是环形链表，遍历将会陷入死循环
总不能等到遍历死循环后再来判断是环形链表吧

这时候我想到了龟兔赛跑的故事
我们可以用一个快指针，一个慢指针来遍历链表
一个每次走2步，一个每次走1步，这样快指针每次就一定会比慢指针快一步

如果是环形链表：那个快指针就一定会先入环，当慢指针也入环后，快指针就会在环中一步一步追上慢指针
如果链表不为环形链表：快指针也无法再次与慢指针相遇，之后就一定会走到空指针

（2）代码演示

这里先创建快慢指针
然后用一个while循环，当fast走到NULL时结束
且当fast==slow时说明已经相遇，是环形链表，接着就只要找入环节点就行了

代码演示：

structListNode*detectCycle(structListNode*head){structListNode*fast=head;//快指针structListNode*slow=head;//慢指针while(fast&&fast->next){ fast=fast->next->next;//每次走2步 slow=slow->next;//每次走一步if(fast==slow)//相等就代表相遇{//F函数为找到入环节点函数（后面会讲）returnF(head,fast);}}//当指针走到空指针就说明不是环形链表，返回NULLreturnNULL;}

3.找到入环节点

（1）思路

现在已知是环形链表，那该怎么找到入环节点呢？

这里为了方便理解，画了一张草图
大家在做算法题的时候也应该多多画图，能更好的理解题目意思

首先设环的长度为C
设非环的长度为L
设相遇点与入环节点的距离为N

我们还可以写出fast和slow走的总距离:
L ( fast ) = L + N + x * C (x为fast走的圈数)
由于fast比slow快，所以slow不可能走完一整圈环，走到一半就会被追上，所以有：
L ( slow ) = L + N

又因为fast的速度是slow的两倍，于是就有L ( fast ) = 2*L ( slow )
带入得：L + N + x * C = 2 * ( L + N )
化简得：x * C = N + L
变式得：( x - 1 ) * C + C - N = L
其中，左式相当于一指针走了（x-1）圈再加上C-N（图上标出了）
而右式就是头节点到入环节点的距离

所以 ! ! !
我们让一个指针meet从fast与slow的相遇点开始走，让一个指针cur从头节点开始走
当meet在环内走了（x-1）圈时，再走C-N距离就会与走了L距离的cur相遇

（2）代码演示

这里先创建meet和cur,分别从相遇点和头节点开始以相同速度走
此时meet和cur的相遇点就是入环节点

structListNode*F(structListNode*head,structListNode*meet){structListNode*cur=head;while(1)//一定会找到，故用死循环，找到时就跳出循环{if(meet==cur){//此时找到，任意返回一个值就行return meet;} meet=meet->next; cur=cur->next;}}

三、考考大家

OK，本文【C语言手撕算法】LeetCode-142. 环形链表 II（C语言）到这里就结束了

但小编在这里给大家留下一个思考问题：
当慢指针的速度为 1 ，而快指针的速度为 3，4， 5…n 时，两指针还会相遇吗？
有没有可能两人错过呢？大家可以去思考思考。

结语

本期资料来自于：

https://leetcode.cn/

OK，本期的【C语言手撕算法】到这里就结束了

若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持

本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！

新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！

支持一下（三连必回QwQ）