临川区建设局网站,详情页设计图片,哔哩哔哩网页版打不开,wordpress页面中英文小图标怎么做目录
1.题目描述和出处
2.分析
3.代码 1.题目描述和出处
LCR 022. 环形链表 II - 力扣#xff08;LeetCode#xff09;
描述很简单#xff0c;寻找交点#xff0c;找到则返回交点#xff0c;找不到返回空。 2.分析
如图#xff1a;#xff08;b表示环的长度#…目录
1.题目描述和出处
2.分析
3.代码 1.题目描述和出处
LCR 022. 环形链表 II - 力扣LeetCode
描述很简单寻找交点找到则返回交点找不到返回空。 2.分析
如图b表示环的长度 本题要使用快慢指针的思想。
定义一个快指针f一个慢指针s。快指针每次从头走两步慢指针从头走一步。若存在环则快指针一定能追上慢指针。 那么现在让快慢指针第一次出发
设f走了2L的距离s走了L的距离(快指针每次从头走两步慢指针从头走一步)。
当f和s相遇时表示f套圈追上了s假设套了n圈则有 2L - L nb - L nb;
若从起点出发到达交点的距离可以用anb来表示而s刚好走了nb的距离也就是说再让s走a的距离就到达了交点但是我们并不知道a的值。 我们第二次需要让快指针重新出发
此时我们让快指针回到起点并且每次直走一步和慢指针保持一致。
那么当他们第二次相遇的时候一定就是交点位置。
原因当f走了a长度的路程时这时b走的距离为nba。
我们有结论anb表示达到交点而n取0就是a。
也就是他们同时到达了交点此时返回任意一个就是最终结果。 3.代码
ListNode *detectCycle(ListNode *head) {//快慢指针ListNode* fhead;ListNode* shead;while(true){//当快指针可以找到末尾时//表示没有环的存在if(f nullptr || f-next nullptr)return nullptr;//快指针走俩步 慢指针走一步ff-next-next;ss-next;if(f s)break;}//从头开始重新找一遍相遇的位置即为交点fhead;while(true){if(f s)break;ff-next;ss-next;}return f;}
