专栏首页Java那些事每天一道leetcode142-寻找链表中环的入口

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

题目

每天一道leetcode142-寻找链表中环的入口 分类:链表 中文链接: https://leetcode-cn.com/problems/linked-list-cycle-ii/ 英文链接 https://leetcode.com/problems/linked-list-cycle-ii/

题目详述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 说明:不允许修改给定的链表。 进阶: 你是否可以不用额外空间解决此题?

题目详解

使用额外空间的思路

  • 就是使用一个hashmap,去遍历一遍链表,每遍历一个链表,如果不存在这个节点,那么就插入hashmap,如果存在,说明这个节点已经插入了,那么这个节点就是重复的节点,为啥重复了,就是环的入口节点了。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashMap<ListNode,Integer> map = new HashMap<>();
        if(head == null || head.next == null)
            return null;
        while(head != null)
        {
            if(map.containsKey(head) == false)
            {
                map.put(head,1);
                head = head.next;
            }else{
                return head;
            }
        }
        return null;
    }
}

代码讲解

  • 15-22行,hashmap判断这个节点如果不存在,那么插入到hashmap里面;
  • 23-24行,hashmap中存在这个节点,那么就返回这个节点,也就是入口节点

不使用额外空间的思路

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

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    boolean flag = true;
    public ListNode detectCycle(ListNode head)
    {
        ListNode pHead = head;
        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;
    }
}

代码讲解

  • 46-76 就是判断链表中是否有环,之前有详细讲过 之前的文章链表:每天一道leetcode141-环形链表
  • 19行中,如果链表有环,那么返回的这个节点必然在环中
  • 22-28行,利用19行的节点,遍历计算环的长度
  • 32-36行,快指针先走环长度
  • 37-41行 快慢指针一起走,相遇就是环的入口节点

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

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

原始发表时间:2018-11-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    乔戈里
  • 每天一道leetcode141-环形链表

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

    乔戈里
  • 手动实现jQuery Tools里面tab功能

    平时开发中用的Javascript类库都是jQuery,用到插件或者第三方类库能从jQuery Tools里面找到,基本不用其他的。当然有时同事喜欢使用jQue...

    八哥
  • 「镁客·请讲」三角兽马宇驰:用技术打通纵横关系,在垂直领域做人工智能语义解决方案

    镁客网
  • C++版 - 剑指offer 面试题15: 链表中倒数第k个结点 题解

    提交网址:  http://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13...

    Enjoy233
  • 轻松搞定链表反转

    最近迫于生活,又去面试咯。好在魔都的就业环境还可以,面试机会总是不缺。今天闲下来了,来谈一谈我最近面试遇到的一道题,是跟反转链表相关的。

    写代码的阿宗
  • 微信跨界开了家人脸智慧时尚店 “刷脸”就能买买买

    微信跨界领域越来越广泛了,这次推出了人脸智慧时尚店,想要帮助顾客实现“刷脸”购物。 ? 12月26日,微信支付、腾讯社交广告与绫致时装集团达成合作,在全国首次推...

    企鹅号小编
  • 无线+4K屏?外媒称HTC Vive 2即将亮相CES 2017

    VRPinea
  • 这里是最全面的 python 字符串拼接总结,赶快收藏!

    在 Python 中字符串连接有多种方式,这里简单做个总结,应该是比较全面的了,方便以后查阅。

    猫咪编程

扫码关注云+社区

领取腾讯云代金券