海南省海口市网站建设,企业年报查询网站,台州seo全网营销,wordpress 彩色序号文章目录 #x1f4a1;题目分析#x1f4a1;解题思路#x1f514;接口源码#x1f4a1;深度思考❓思考1❓思考2 题目链接#x1f449;
LeetCode 141.环形链表#x1f448; #x1f4a1;题目分析 给你一个链表的头节点 head #xff0c;判断链表中是否有环。 如果链表中… 文章目录 题目分析解题思路接口源码深度思考❓思考1❓思考2 题目链接
LeetCode 141.环形链表 题目分析 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 解题思路 快慢指针 定义两个指针一个快指针、一个慢指针让快指针一次走一步慢指针一次走两步如果存在环的话快指针会先进环一直在环中循环的走等到慢指针也进入环中循环快指针追击慢指针最后它们一定会相遇因为快慢指针的差距步是一步就可以判断出该链表存在环如果不存在环的话快指针会走到头结束。 过程图解
接口源码
//快慢指针
bool hasCycle(struct ListNode *head)
{struct ListNode* fast head, *slow head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){return true;}}return false;
}深度思考
❓思考1
slow一次走一步fast一次走两步slow和fast一定会相遇吗 fast会先进环slow会后进环假设slow进环时slow和fast之间的距离为Nslow进环以后fast开始追击slowslow每走1步fast每走2步他们之间距离缩小1。 追击过程中他们之间的距离变化NN-1N-2… 210 所以一定会相遇 ❓思考2
slow一次走一步fast一次走三步slow和fast一定会相遇吗 fast会先进环slow会后进环假设slow进环时slow和fast之间的距离Nslow进环以后fast开始追击slowslow每走1步fast每走3步他们之间距离缩小2 由于环的长度不同追击过程中他们之间的距离变化会有两种情况奇/偶 所以不一定会相遇 希望烙铁们能够理解欧 总结 以上就是本题讲解的全部内容啦 本文章所在【C/C刷题系列】专栏感兴趣的烙铁可以订阅本专栏哦 前途很远也很暗但是不要怕不怕的人面前才有路。 小的会继续学习继续努力带来更好的作品 创作写文不易还多请各位大佬uu们多多支持哦
