链表返回环的入口节点

矫情吗；* 2022-12-21 04:43 169阅读 0赞

**题目描述**  
对于一个给定的链表，返回环的入口节点，如果没有环，返回null  
拓展：  
你能给出不利用额外空间的解法么？

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

https://blog.nowcoder.net/n/954373f213e14eeab0a69ed0e9ef1b6e

class ListNode{
        
     int val;
     ListNode next;
     ListNode(int x){
        
       val=x;
       next=null
     }
    }

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    //思路：1. 利用款慢指针判断是否存在环，如果快指针最后指向NULL,则不存在环，否则存在环
    //     2. 利用双指针判读入口节点。让两个指针分别以相同的速度前进，两个指针再次相遇的位置即为换的入口节点
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode slow=head, fast=head;
            while(fast!=null&&fast.next!=null){
        
                fast=fast.next.next;//每次走两步
                slow=slow.next;//每次走一步
                //相遇了！！则存在环
                if(fast==slow){
        
                    ListNode slow2=head;
                    //一个从开始，另一个从相遇开始。如何相遇则是如何看
                    while(slow!=slow2){
        
                        slow=slow.next;
                        slow2=slow2.next;
                    }
                    return slow;
                }
                
            }
            return null;
                
            
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关链表中环的入口节点

计算链表中环的节点数和环的入口节点利用快慢指针可以解决这个问题（看下面的代码） //链表的结构类型 struct ListNode { int

柔光的暖阳◎/ 2023年03月02日 10:22/ 0 赞/ 15 阅读

相关 28：链表中环的入口节点

链表中环的入口节点如果一个链表中包含环，如何找出环的入口节点？ public class Offer29 { public static vo

r囧r小猫/ 2023年03月01日 10:11/ 0 赞/ 2 阅读

相关链表返回环的入口节点

题目描述对于一个给定的链表，返回环的入口节点，如果没有环，返回null 拓展：你能给出不利用额外空间的解法么？说明：本题目包含复杂数据结构ListNode，

矫情吗；*/ 2022年12月21日 04:43/ 0 赞/ 170 阅读

相关链表中环的入口节点

链表中环的入口节点 1、参考资料 https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425a

Dear 丶/ 2022年12月05日 00:56/ 0 赞/ 197 阅读

相关链表中环的入口节点

[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Ft

柔光的暖阳◎/ 2022年11月30日 04:20/ 0 赞/ 203 阅读

相关判断链表是否有环、找到环的入口节点

昨天去完美笔试的时候遇到以前见过的老题目，记录一下吧... 题目很简单，就是说：给你一个链表，判断是否存在环！同时求出环的入口节点！

迈不过友情╰/ 2022年09月17日 12:23/ 0 赞/ 225 阅读

相关链表问题_链表中环的入口节点

题目：一个链表中包含环路，求链表的入口节点。分析：根据求[链表中倒数第K个节点][K]的方法，这个问题可以分为两个步骤：1、判断链表中的节点个数记为K，对于这个可以采用一

矫情吗；*/ 2022年05月21日 07:23/ 0 赞/ 247 阅读

相关链表中环的入口节点

问题描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。有环链表类似于下图中的链表： ![70][] 可以看到该链表中有一个环，其中橙

缺乏、安全感/ 2022年05月14日 03:56/ 0 赞/ 222 阅读

相关【题23 链表中环的入口节点】

【题23 链表中环的入口节点】【题目】如果一个链表中包含环，如何找出环的入口节点？例如：如图的链表中，环的入口节点是节点3 分析： 1. 如何确定

冷不防/ 2022年03月25日 03:14/ 0 赞/ 227 阅读

相关链表之查找环的入口节点

思路：设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一

亦凉/ 2021年09月18日 04:56/ 0 赞/ 662 阅读