LeetCode：Linked List Cycle II 链表回环入口处

淩亂°似流年 2021-06-11 15:14 294阅读 0赞

**试题：**  
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.  
Example 1:  
Input: head = \[3,2,0,-4\], pos = 1  
Output: tail connects to node index 1  
Explanation: There is a cycle in the linked list, where tail connects to the second node.  
Example 2:  
Input: head = \[1,2\], pos = 0  
Output: tail connects to node index 0  
Explanation: There is a cycle in the linked list, where tail connects to the first node.  
Example 3:  
Input: head = \[1\], pos = -1  
Output: no cycle  
Explanation: There is no cycle in the linked list  
Follow up:  
Can you solve it without using extra space?  
**代码：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjM0NjEz_size_16_color_FFFFFF_t_70]  
1、单链表有环，那么进入环内的指针只能在环内移动；  
2、如果指针p1每次走一步，而p2每次走两步，那么p1和p2一定会在环内相遇，以此判断有环；物理题：两人速度相差为1，绕圈跑。  
3、而且p2不需要再跑完一圈就能追上p1，因为p1到达入口时，p2与p1距离不足一圈，只要再跑距离差就能追上。  
4、那如何判断环的入点?p2的速度是p1速度的两倍，当p1和p2相遇时，p2比p1多跑一倍距离。也就是说p2跑了2(s+r)=s+r+n\*(r+l)距离（C为相遇点，n为跑的圈数），显然n=1，s=l，n>1时走s的距离相当于在圈内跑n-1圈+l的距离，刚好又到入口点s=(n-1)(r+l) + l

/**
     * 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) {
    //         保证至少有两个节点
            if (head == null || head.next == null) return null;
    
            ListNode firstp = head;
            ListNode secondp = head;
            boolean isCycle = false;
    
    //         遍历链表知道
            while(secondp != null) {
    //             走一步
                firstp = firstp.next;
    //             如果secondP走到底那就说明没环
                if (secondp.next == null) return null;
    //             走两步
                secondp = secondp.next.next;
                if (firstp == secondp) { isCycle = true; break; }
            }
    
            if(!isCycle) return null;
            firstp = head;
            while( firstp != secondp) {
                firstp = firstp.next;
                secondp = secondp.next;
            }
    
            return firstp;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjM0NjEz_size_16_color_FFFFFF_t_70]: /images/20210520/a9a7db3f42fe4a7cb7477593295cafc5.png

发表评论取消回复

表情：

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

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

相关阅读

相关 141. Linked List Cycle （判断单链表中是否有环）

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it

╰半夏微凉°/ 2022年07月15日 01:20/ 0 赞/ 131 阅读

相关 141. Linked List Cycle （判断单链表中是否有环）

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it

拼搏现实的明天。/ 2022年07月15日 01:20/ 0 赞/ 119 阅读

相关 [Leetcode][python]Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II

Linked List Cycle 题目大意判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？解题思路哈希表快慢指针代码

雨点打透心脏的1/2处/ 2022年06月04日 01:59/ 0 赞/ 179 阅读

相关 LeetCode刷题笔记（链表）：linked-list-cycle-ii

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

骑猪看日落/ 2022年06月01日 00:39/ 0 赞/ 151 阅读

相关 LeetCode 142.Linked List Cycle II (环形链表 II) 详解

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

约定不等于承诺〃/ 2022年05月08日 13:22/ 0 赞/ 161 阅读

相关 LeetCode：142. Linked List Cycle II（找出链表中的环）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

分手后的思念是犯贱/ 2022年04月05日 09:10/ 0 赞/ 161 阅读

相关 [LeetCode]linked-list-cycle ii 环形链表

问题描述 Given a linked list, return the node where the cycle begins. If there is no cycl

忘是亡心i/ 2022年03月18日 21:14/ 0 赞/ 178 阅读

相关【Leetcode】141. Linked List Cycle（链表判环）

Given a linked list, determine if it has a cycle in it. To represent a cycle in the giv

桃扇骨/ 2022年02月09日 09:57/ 0 赞/ 215 阅读

相关 LeetCode: 141. Linked List Cycle 链表是否有环

试题： Given a linked list, determine if it has a cycle in it. To represent a cycle in t

柔情只为你懂/ 2021年06月24日 16:10/ 0 赞/ 337 阅读

相关 LeetCode：Linked List Cycle II 链表回环入口处

试题： Given a linked list, return the node where the cycle begins. If there is no cycle,

淩亂°似流年/ 2021年06月11日 15:14/ 0 赞/ 295 阅读