网站建设数据库放哪,最近热搜新闻事件,广州市公司网站建设报价,同学录网站开发的背景1.前言
前五题在这http://t.csdnimg.cn/UeggB
后三题在这http://t.csdnimg.cn/gbohQ
记录每天的刷题#xff0c;继续坚持#xff01;
2.OJ题目训练
9. 给定一个链表#xff0c;判断链表中是否有环。
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成…1.前言
前五题在这http://t.csdnimg.cn/UeggB
后三题在这http://t.csdnimg.cn/gbohQ
记录每天的刷题继续坚持
2.OJ题目训练
9. 给定一个链表判断链表中是否有环。
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路
快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表其实位置开始运行 如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。比如操场跑步 以这个环形链表距离当我们指针进环后相当于进入了2 0 -4的循环我们可以将这三步类比成在环形操场跑步 可以假设A和B在操场同一个起点开始跑步A的速度是一次跑一米B的速度是一次跑两米 以此来进行当A跑半圈时B已经跑完一圈了而当A跑一圈时B也跑完两圈了这样他们就在起点相遇了。 我们就可以利用这一特性类比到环形数组中。
注意要点
环形链表是没有尾指针的没有下一个节点为NULL,利用这个特性我们第一步可以很轻松的判断是否为环形节点避免越界访问限制条件
附源代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode *first head ,*slow head;while(first!NULLfirst-next!NULL slow-next!NULL) //防止越界访问报错{first first-next-next; slow slow-next;if(first slow){return true;}}return false;
}
【扩展问题】
为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚 进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。 此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情 况因此在满指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 快指针一次走3步走4步...n步行吗
