【数据结构和算法】快慢指针以及集合两种方式解决

链表中环的入口节点

http://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad

这题可以参照《判断链表中是否有环》 ,答案我之前写过《链表是否有环3种方式解决》 ,这两道题有非常大的相似地方。

1,快慢指针解决

在前面我们提到过快慢指针,先判断是否有环,如果有环,在来找环的入口。我们假设是有环的,那么会有两种情况,我们来画个图看一下

1,环很大

image.png
假如他们在相遇点相遇了,那么慢指针走过的距离是a+b,快指针走过的距离就是a+b+c+b,因为相同时间内快指针走的距离是慢指针的2倍,所以有a+b+c+b = 2*(a+b),整理得到a=c,也就是说从相遇点到环的入口和链表的起始点到环的入口,距离是一样的。在相遇点的时候我们可以使用两个指针,一个从相遇点开始,一个从链表头开始,他们每次都走一步,直到他们再次相遇位置,那么这个相遇点就是环的入口。

2,环很小

image.png
那么这种情况,快指针在环上转了好几圈了,慢指针才走到环上,假如快指针在环上已经走了m圈了,慢指针在环上走了n圈,他们最终在环上相遇,那么

慢指针走过的距离是:a+b+n*(b+c) (b+c其实就是环的长度)
快指针走过的距离是:a+b+m*(b+c)

在相同的时间内快指针走过的距离是慢指针的2倍,所以有
a+b+m*(b+c) = 2*(a+b+n*(b+c))

整理得到
a+b=(m-2n)(b+c),

上面b+c其实是环的长度,也就是说a+b等于(m-2n)个环的长度,这个时候我们还可以使用两个指针一个从相遇点开始,一个从链表头开始,这时候就会出现一个现象就是一个指针在链表上走,一个指针在环上转圈,最终会走到第1种情况,就是环很小(我们可以认为链表前面减去m-2n-1个环的长度就是第一种情况了)

搞懂了上面的分析过程,我们来看下代码

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            //快慢指针,快指针每次走两步,慢指针每次走一步
            fast = fast.next.next;
            slow = slow.next;
            //先判断是否有环,
            if (slow == fast) {
                //确定有环之后才能找环的入口
                while (head != slow) {
                    //两相遇指针,一个从头结点开始,
                    //一个从相遇点开始每次走一步,直到
                    //再次相遇为止
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

2,存放到集合中

可以参照之前的题,把节点放入到集合中,如果有环,就会出现重复的,然后返回第一个重复的节点即可

    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            //如果重复出现说明有环
            if (!set.add(head))
                return head;
            //否则就把当前节点加入到集合中
            head = head.next;
        }
        return null;
    }

我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解

数据结构和算法 文章被收录于专栏

专注于算法题的讲解,包含常见数据结构,排序,查找,动态规划,回溯算法,贪心算法,双指针,BFS和DFS等等

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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
2022-12-27 14:49
韶关学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-10 09:46
宁夏大学_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-31 20:32
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
10 收藏 评论
分享

全站热榜

正在热议