---
title: "环形链表2"
created: 2025-11-28
tags:
  - 算法
---

# 环形链表2

## 题目 [环形链表2](https://leetcode.cn/problems/linked-list-cycle-ii/description/)

![[image-b1fc20a2.png]]

## 思路分析

![[image-a9d9fc30.png]]

由上一题可以得知若存在环就一定会相遇

那么假定相遇的位置为c点

入口点为b点 我要想办法找到这个b点

那么 让slow指针往回退到b点 也就是退y个距离 那么fast在那个时间点就应该在c-2y的地方（退2y个距离）

![[image-1bf31568.png]]

也就是说 在slow走了x长度的时候 fast（2倍速的slow）走到了d这个点 走了两倍的x长度

那去掉重复的ab那一段 多出来的不也就是x长吗

也就是说 x长度可以绕这个环n圈后 到了3/4位置处j

（只是对于当前图d点的解释 示例在3/4处好理解 其实是以d→b = b→c = y来判断的）

![[image-3e15add6.png]]

那么也就是说 我x可以绕这个环走n圈多3/4圈 至于n是多少无所谓

而c点是在1/4处的 是不是可以刚好和那3/4补满一圈？

（真实情况是 c在入口y处 x能绕圈走n圈差y到下一圈）

那么意思就是 我从c处 再走一个x 就一定能到b点咯

所以当相遇时 可以把其中任意一个指针回到起点

再把两个指针以同样的速度去走

那个指针下一次相遇时

就是我们的环的入口

## 代码实现

```java
 class Solution {

 public:

  ListNode* detectCycle(ListNode* head) {

    ListNode* slow = head;

    ListNode* fast = head;

    while (fast && fast->next) {

      slow = slow->next;

      fast = fast->next->next;

      if (slow == fast) {

        slow = head;

        while (slow != fast) {

          slow = slow->next;

          fast = fast->next;

        }

        return slow;

      }

    }

    return nullptr;

  }

};
```

## 同类题型

## 视频讲解

---
⬅️ [[环形链表|环形链表]] 🏠 [[00-刷题理模型]] ➡️ [[k倍区间|k倍区间]]