专栏首页Java那些事每天一道剑指offer-链表中环的入口结点

每天一道剑指offer-链表中环的入口结点

考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默响起来一个声音:”乔戈里峰

题目

每天一道剑指offer-链表中环的入口结点 https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目详述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

题目详解

思路

  • 使用快慢指针,快指针每次走两步,慢指针每次走一步,如果快慢指针相遇说明有环;
  • 有环以后,需要寻找环入口节点,已经找到了一个环的中的节点,利用这个节点,去往下遍历,由于是环,所以这个节点肯定会和自身相遇,相遇以后,记录相遇过程中走的步数,就是环的长度
  • 知道环的长度以后,然后再利用快慢指针的思想,快指针先走环长度,然后快慢指针再一起走,这样因为快指针先走了环的长度,当两者相遇肯定是环的入口节点相遇(为啥呢,因为快慢指针肯定会进入环里面,而由于快指针先走了环的长度,所以也就是一个周期,所以只要进入环,那么这两个指针必然相遇)

代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    boolean flag = true;
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return null;
        ListNode pNode = judgeHasChain(pHead);//判断是否有环
        if(pNode != null)
        {
            int lengthChain = 1;
            ListNode pNodeCopy = pNode.next;
            while(pNodeCopy != pNode)
            {//这个节点已经在环里面了!
                lengthChain++;
                pNodeCopy = pNodeCopy.next;//计算环的长度
            }
            ListNode fast = pHead;
            ListNode slow = pHead;
            int temp = 0;
            while(temp < lengthChain)
            {//快指针先走环的长度
                fast = fast.next;
                temp++;
            }
            while(fast != slow)
            {//快慢指针一起走,因为快指针先走了环长度,当慢指针刚一进环,由于快指针刚好多走了环长度,所以快指针整好走了一个环的周期呀,所以快指针必然也在环的入口
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }
    private ListNode judgeHasChain(ListNode pHead)
    {
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != slow)
        {
            if(fast != null && fast.next != null)
            {//快指针走一步
                fast = fast.next;
            }else{
                flag = false;
                break;
            }
            if(slow != null && slow.next != null)
            {//慢指针走一步
                slow = slow.next;
            }else{
                flag = false;
                break;
            }
            if(fast == slow)
            {//两者相等,说明相遇了,有环
                return fast;
            }else{
                fast = fast.next;//快指针多走一步
            }
        }
        if(flag)
            return fast;
        return null;
    }
}

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode142-寻找链表中环的入口

    乔戈里
  • 每天一道leetcode19-删除链表的倒数第N个节点

    乔戈里
  • 每天一道剑指offer-反转链表

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • FreeRTOS 任务调度 任务切换

    前面文章 < FreeRTOS 任务调度 任务创建 > 介绍了 FreeRTOS 中如何创建任务以及其具体实现。 一般来说, 我们会在程序开始先创建若干个任务...

    orientlu
  • java 避免出现NullPointerException(空指针)的方法总结

    Java应用中抛出的空指针异常是解决空指针的最好方式,也是写出能顺利工作的健壮程序的关键。俗话说“预防胜于治疗”,对于这么令人讨厌的空指针异常,这句话也是成立的...

    林老师带你学编程
  • 双指针法:总结篇!

    相信大家已经对双指针法很熟悉了,但是双指针法并不隶属于某一种数据结构,我们在讲解数组,链表,字符串都用到了双指针法,所有有必要针对双指针法做一个总结。

    代码随想录
  • 前端常见技术点-Javascript扫盲(26问)

    这里总结一下 WEB 前端面试 JS 部分的常见问题,同时这些问题也是对一些基础的技术概念和思想的理解。对这些基本知识的掌握程度和深度决定了你的技术层级。高级工...

    用户5997198
  • 今年春节,推荐三个 AI 工具为你写春联

    盼望着,盼望着,春节就要来了,今年春节有什么值得期待的事情么?不如趁着爸妈还没来得及催婚催生之前,先好好在家里表现一番。

    HyperAI超神经
  • Go进阶05:不安全指针unsafe.Pointer使用

    在大家学习 Go 的时候,肯定都学过 “Go 的指针是不支持指针运算和转换” 这个知识点.为什么呢?

    mojocn
  • LongAccumulator介绍,使用,实现原理

    LongAdder类时LongAccumulator的一个特例,LongAccumulator比LongAdder的功能更强大。例如下面的构造函数,其中accu...

    YanL

扫码关注云+社区

领取腾讯云代金券