【Java版oj】环形链表 II

古城微笑少年丶 2024-04-01 09:43 69阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [142. 环形链表 II][142. _ II]
> 
> 难度中等1822
> 
> 给定一个链表的头节点 `head` ，返回链表开始入环的第一个节点。 *如果链表无环，则返回 `null`。*
> 
> 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（**索引从 0 开始**）。如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。
> 
> **不允许修改** 链表。
> 
> **示例 1：**
> 
> ![1c6273e06aaa6ca7c4d91bb726b28e83.png][]
> 
>     输入：head = [3,2,0,-4], pos = 1
>     输出：返回索引为 1 的链表节点
>     解释：链表中有一个环，其尾部连接到第二个节点。
> 
> **示例 2：**
> 
> ![dfcc62169f38aadc0807ffed6fde89d0.png][]
> 
>     输入：head = [1,2], pos = 0
>     输出：返回索引为 0 的链表节点
>     解释：链表中有一个环，其尾部连接到第一个节点。
> 
> **示例 3：**
> 
> ![ea8717d9113cbaa51cbc269b5ce245ba.png][]
> 
>     输入：head = [1], pos = -1
>     输出：返回 null
>     解释：链表中没有环。
> 
> **提示：**
> 
>  *  链表中节点的数目范围在范围 `[0, 104]` 内
>  *  `-105 <= Node.val <= 105`
>  *  `pos` 的值为 `-1` 或者链表中的一个有效索引

> ## 二、问题分析 ##
> 
> 前情提要：指路环形链表☞[http://t.csdn.cn/KiTvN][http_t.csdn.cn_KiTvN] [141. 环形链表][141.]
> 
>  说明：
> 
> H为链表的起始点，E为环入口点，M为与判环时候相遇点
> 
>  假设：
> 
> 环的长度为R，H到E的距离为L，E到M的距离为X，则：M到E的距离为R-X
> 
> 在判环时，快慢指针相遇时所走的路径长度:fast:L +X + nR;slow:L + X  
>  注意：  
> 1.当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1。因为快指针先进环走到M的位置，最后又在M的位置与慢指针相遇  
> 2.慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针。因为慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们至今的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。
> 
> 而快指针速度是慢指针的两倍，因此有如下关系是:  
> 2\*(L+ X)=L+X+ nR  
> L+X=nR  
> L= nR-X (n为1,.,3...... n的大小取决于环的大小，环越小n越大)  
> 极端情况下，假设n= 1,此时:L= R-X  
> 即:一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇
> 
> 结论：L= R-X
> 
> 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
> 
> ![95b3bac269034818995c66238c303694.png][]

> ## 三、完整代码 ##
> 
>     /**
>      * 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) {
>             
>             ListNode fast = head;
>             ListNode slow = head;
>     
>             while (true) {
>                 if (fast == null) {
>                     break;
>                 }
>                 fast = fast.next;
>                 slow = slow.next;
>                 if (fast == null) {
>                     break;
>                 }
>                 fast = fast.next;
>     
>                 if (fast == slow) {
>                     break;
>                 }
>             }
>     
>             // fast == null || fast == slow
>             // fast == null : 链表不带环
>             // fast == slow : 链表带环
>             if (fast == null) {
>                 return null;
>             }
>     
>             // fast == slow 相等，都指向相遇点
>             ListNode c1 = head;
>             ListNode c2 = fast;
>     
>             while (c1 != c2) {
>                 c1 = c1.next;
>                 c2 = c2.next;
>             }
>     
>             return c1;     
>         }
>     }

--------------------

![7085a18777bb45bbbc37599de1cd28c1.png][]

[142. _ II]: https://leetcode.cn/problems/linked-list-cycle-ii/
[1c6273e06aaa6ca7c4d91bb726b28e83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cf9affa6c0d44735bc045762bd58a2a9.png
[dfcc62169f38aadc0807ffed6fde89d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d80aeb467ab84142b17310d9ef107b0f.png
[ea8717d9113cbaa51cbc269b5ce245ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/57e82d94d49e42f9b1c087e5df5763f9.png
[http_t.csdn.cn_KiTvN]: http://t.csdn.cn/KiTvN
[141.]: https://leetcode.cn/problems/linked-list-cycle/
[95b3bac269034818995c66238c303694.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0ab4c089434b4faa8fa2a56c2cb334c2.png
[7085a18777bb45bbbc37599de1cd28c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/15966c43ab324a178885ee7c3c27dfec.png