记录刷题笔记快慢指针:环形指针
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }

       
    ListNode fast=head,slow=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next.next;
            }else{return null;}

           if(fast==slow){
               ListNode str=head;
               while(str!=slow){
                   str=str.next;
                   slow=slow.next;

               }
               return str;
           }
        }
        return null;
    }
}

我们使用两个指针,fast 与}slow。它们起始都位于链表的头部。随后,\textit{slow}slow 指针每次向后移动一个位置,而 \textit{fast}fast 指针向后移动两个位置。如果链表中存在环,则 \textit{fast}fast 指针最终将再次与 \textit{slow}slow 指针在环中相遇。

设链表中环外部分的长度为 aa。\slow 指针进入环后,又走了 bb 的距离与 fast 相遇。此时,fast 指针已经走完了环的 nn 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc。

根据题意,任意时刻,\textit{fast}fast 指针走过的距离都为slow 指针的 2 倍。因此,我们有

a+(n+1)b+nc=2(a+b)⟹  a=c+(n-1)(b+c)
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1n−1 圈的环长,恰好等于从链表头部到入环点的距离。

因此,当发现 slow 与 \}fast 相遇时,我们再额外使用一个指针ptr。起始,它指向链表头部;随后,它和 \textit{slow}slow 每次向后移动一个位置。最终,它们会在入环点相遇。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
来源:力扣(LeetCode)

侵删

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议