专栏首页desperate633LeetCode 142. Linked List Cycle II题目分析代码

LeetCode 142. Linked List Cycle II题目分析代码

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space?

题目

给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。

分析

我们画图具体分析

Paste_Image.png

首先,使用两个指针slow,fast。两个指针都从表头开始走,slow每次走一步,fast每次走两步,如果fast遇到null,则说明没有环,返回false;如果slow==fast,说明有环,并且此时fast超了slow一圈,返回true。

链表头是X,环的第一个节点是Y,slow和fast第一次的交点是Z。各段的长度分别是a,b,c,如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。

因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。

我们发现L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度

我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。

代码

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {  
        if(head == null || head.next == null)
            return null;
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while(slow != fast) {
            if(fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        slow = head;
        fast = fast.next;
        
        while(slow!=fast) {
            slow = slow.next;
            fast =fast.next;
        }
        
        return slow;
    
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 141. Linked List Cycle题目Approach #1 (Two Pointers)代码Approach #2 (Hash Table)

    使用两个指针slow,fast。两个指针都从表头开始走,slow每次走一步,fast每次走两步,如果fast遇到null,则说明没有环,返回false;如果sl...

    desperate633
  • LintCode 删除排序链表中的重复元素题目

    desperate633
  • LintCode 旋转链表题目分析代码

    样例 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null

    desperate633
  • Leetcode: Linked List Cycle II

    题目: Given a linked list, return the node where the cycle begins. If there is n...

    卡尔曼和玻尔兹曼谁曼
  • 数据结构基础温故-3.队列

    在日常生活中,队列的例子比比皆是,例如在车展排队买票,排在队头的处理完离开,后来的必须在队尾排队等候。在程序设计中,队列也有着广泛的应用,例如计算机的任务调度系...

    Edison Zhou
  • 【NSR特别专题】张坤:学习因果关系和基于因果关系的学习「全文翻译」

    编者按:《国家科学评论》于2018年1月发表“机器学习”特别专题,由周志华教授组织并撰写文章。专题内容还包括对AAAI前主席Tom Dietterich的访谈,...

    马上科普尚尚
  • java日志组件介绍(common-logging,log4j,slf4j,logback )

    复制来源:java日志组件介绍(common-logging,log4j,slf4j,logback ) common-logging common-loggi...

    Ryan-Miao
  • ​Wiztalk 腾讯犀牛鸟项目学术分享之观测数据下因果推断

    8月14日(本周五)19:00,我们将邀请浙江大学计算机学院况琨老师分享观测数据下因果推断的相关工作。况琨老师2019年获得清华大学计算机科学与技术专业博士学...

    腾讯高校合作
  • 一文让你入门CNN,附3份深度学习视频资源

    CNN简介 文末附三份深度学习视频资源 后台回复关键词(20180310) 目录: 一些视频资源和文章 CNN简介 图像即四维张量? 卷积的定义 CNN如何工作...

    昱良
  • HTTP协议基础学习

    版权声明:本文为木偶人shaon原创文章,转载请注明原文地址,非常感谢。 https://b...

    shaonbean

扫码关注云+社区

领取腾讯云代金券