免费行情软件网站下载企业宣传网站源码

免费行情软件网站下载,企业宣传网站源码,临沂做网站系统,做网站主播要什么条件【C语言手撕算法】LeetCode-142. 环形链表 II#xff08;C语言#xff09;一、题目介绍二、题目详解1.审题2.判断是否为环形链表#xff08;1#xff09;思路#xff08;2#xff09;代码演示3.找到入环节点#xff08;1#xff09;思路#xff08;2#xff09;代码演…【C语言手撕算法】LeetCode-142. 环形链表 IIC语言一、题目介绍二、题目详解1.审题2.判断是否为环形链表1思路2代码演示3.找到入环节点1思路2代码演示三、考考大家结语前言本专栏将给大家带来一些有意思的算法题希望对大家有所帮助若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持!!!谢谢大家 ! ! !一、题目介绍本篇是小编从leetcode上挑选的一道例题同时还是一道难度较大的面试题就让我们来手撕这道面试题吧下面是题目链接LeetCode-142. 环形链表 II二、题目详解1.审题老规矩拿到题目先审题题目要求返回链表开始入环的第一个节点所以首先我们要判断该链表是否为环形链表如果不是那直接返回NULL就行了若是环形链表该想办法找出返回链表开始入环的第一个节点下面我一步一步带大家解出此题2.判断是否为环形链表1思路如果链表不为环形链表遍历链表就一定会走到空指针但是如果是环形链表遍历将会陷入死循环总不能等到遍历死循环后再来判断是环形链表吧这时候我想到了龟兔赛跑的故事我们可以用一个快指针一个慢指针来遍历链表一个每次走2步一个每次走1步这样快指针每次就一定会比慢指针快一步如果是环形链表那个快指针就一定会先入环当慢指针也入环后快指针就会在环中一步一步追上慢指针如果链表不为环形链表快指针也无法再次与慢指针相遇之后就一定会走到空指针2代码演示这里先创建快慢指针然后用一个while循环当fast走到NULL时结束且当fastslow时说明已经相遇是环形链表接着就只要找入环节点就行了代码演示structListNode*detectCycle(structListNode*head){structListNode*fasthead;//快指针structListNode*slowhead;//慢指针while(fastfast-next){fastfast-next-next;//每次走2步slowslow-next;//每次走一步if(fastslow)//相等就代表相遇{//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*curhead;while(1)//一定会找到故用死循环找到时就跳出循环{if(meetcur){//此时找到任意返回一个值就行returnmeet;}meetmeet-next;curcur-next;}}三、考考大家OK本文【C语言手撕算法】LeetCode-142. 环形链表 IIC语言到这里就结束了但小编在这里给大家留下一个思考问题当慢指针的速度为 1 而快指针的速度为 34 5…n 时两指针还会相遇吗有没有可能两人错过呢大家可以去思考思考。结语本期资料来自于https://leetcode.cn/OK本期的【C语言手撕算法】到这里就结束了若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持本文有若有不足之处希望各位兄弟们能给出宝贵的意见。谢谢大家新人本期制作不易希望各位兄弟们能动动小手三连走一走支持一下三连必回QwQ