链表返回环的入口节点

矫情吗；* 2022-12-21 04:43 133阅读 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 条评论，133人围观）

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

相关阅读

相关牛客-链表中环的入口节点(Java)

链表中环的入口节点【题目描述】对于一个给定的链表，返回环的入口节点，如果没有环，返回null 【思路】 1. 首先判断有没有环我们可以设置两个指针

待我称王封你为后i/ 2023年10月04日 12:59/ 0 赞/ 11 阅读

相关 java单链表是否存在环及环的入口节点

思路：是否存在环：快慢指针来判断是否存在环，快指针每次走两步，慢指针每次走一步，快慢指针相遇，即存在环环入口节点：快慢指针相遇后，慢指针回到头节点，快指针每次走一步

Love The Way You Lie/ 2023年06月08日 06:51/ 0 赞/ 7 阅读

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

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

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

相关链表中环的入口节点

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

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

相关链表中环的入口节点

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

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

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

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

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

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

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

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

相关链表中环的入口节点

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

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

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

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

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

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

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

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