• 热度指数：40754 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Can you solve it without using extra space?

2）将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)。

2*(a + b) = a + b + n * (b + c)；即
a=(n - 1) * b + n * c = (n - 1)(b + c) +c;

```class Solution {
public:
ListNode *detectCycle(ListNode *head) {
return 0;
}
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
break;
}
}
if(fast == NULL || fast->next == NULL){
return NULL;
}
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};```

```package linkedlist;
/**
* 题目描述: 链表的入环节点，如果无环，返回null
* Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
* Follow up: Can you solve it without using extra space?
* 思路：
* 1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null
* 2）有环的情况下， 求链表的入环节点
*   fast再次从头出发，每次走一步，
*   slow从相遇点出发，每次走一步，
*   再次相遇即为环入口点。
* 注：此方法在牛客BAT算法课链表的部分有讲解。
*/
//nowcoder pass
public class Solution {

public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}

ListNode meetNode = meetingNode(head);
if (meetNode == null) {//说明无环
return null;
}

ListNode fast = head;
ListNode slow = meetNode;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}

return slow;
}

//寻找相遇节点，如果无环，返回null
public ListNode meetingNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return slow;
}
}
return null;
}
}```

slow： 走过 x 个节点
fast：走过2x 个节点

slow走过的距离为 x = a + b + n*(b + c);   (2)

n>0时，a+b = (1-n)*(b+c) <= 0,不成立。故n = 0,得出：a = c。

```/**

1.还是先用快慢指针方法，找出快慢指针相遇的点；
3.两个指针每次走一步，相遇点则是链表环的起点；
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode node1 = head;
ListNode node2 = fast;
while(node1 != node2){
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
}
return null;
}
}```

1.首先判断是否存在环
2.若存在环，则从起点开始，每走一步就删除上一个节点的next指针，最后一个节点就是环的起点。因为环的起点会存在两个next指向它。

``````ListNode *detectCycle(ListNode *head) {//每次前进的时候删除上一个指针
return NULL;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
break;
}
if(fast == NULL||fast->next==NULL)
return NULL;

while(cur!=NULL){
if(pre==cur)
return pre;
pre->next=NULL;
pre=cur;
cur=cur->next;
}
return pre;

}
``````

@wangxiaotao的图不错，借用一下，公式不太清楚。

```ListNode *detectCycle(ListNode *h) {
ListNode *p = h, *q = h;
while (q && q->next) {
p = p->next;
q = q->next->next;
if (p == q) {
while (h != q) {
q = q->next;
h = h->next;
}
return h;
}
}

return NULL;
}```

```public class Solution {
/*
* 思路：
* 1）首先判断是否有环，有环时，返回相遇的节点，无环，返回null
* 2）有环的情况下，求链表的入环节点
*    fast再次从头出发，每次走一步，slow从相遇点出发，每次走一步，再次相遇即为环入口点。
*/
public ListNode detectCycle(ListNode head) {
if(head == null) return null;

ListNode slow = head;
ListNode fast = head;
ListNode meetNode = null;
while(fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) { //快慢指针相遇，说明有环，记录相遇节点，跳出循环
meetNode = slow;
break;
}
}
if(meetNode == null) return null; //相遇节点为空，说明无环，返回null

fast = head; //fast再次从头出发
while(slow != fast) { //再次相遇即为环入口点
slow = slow.next; //slow每次走一步
fast = fast.next; //fast每次走一步
}
return slow;
}
}```

1.用指针temp指向当前待确定的节点,用pre指向待确定节点的上一个节点。由于在遇到环的入口之前，前面的节点均不可能重复，所以待确定节点的上一个节点一定还未遇到。那么每次从头节点开始，至待确定节点的前一个节点，用指针依次遍历，在此之间如果指向地址等于待确定节点地址，则说明待确定节点第二次遇到，为环，入口即为待确定节点。

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *temp,*top,*pre;
bool flag=false;
while(temp) {
while(top!=pre) {
top=top->next;  //如果还未到待确定节点前一节点就继续
}
if(flag) return temp;  //返回入口
else {
pre=pre->next;
temp=temp->next;
}
}
return NULL;
}
};

```public class Solution {
public ListNode detectCycle(ListNode head) {
/* 快慢指针，第一次相遇快指针走过的是慢指针的两倍
* head到环起始位置为l, 环周长为r, 第一次相遇点在环起点后x
* s = l + x; 2s = l + r + x; => l + x = r; => l = r - x;
*/
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast==null||fast.next==null) return null;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}```

```/** 一个新思路，可能没有满足不使用额外空间的要求，不过使用的也不多
毕竟大多数牛友所述的Floyd判圆算法不是第一次就能够轻易想出来的

1. 先利用快慢指针判断是否存在环，并在这个过程中对快指针走过的结点数计数，假设为2*count
2. 从链表中第一个结点开始指定，依次让慢指针走2*count步，如果没有与指定结点相遇，就让指定结点向后移动
3. 当第一次出现慢指针与指定结点相遇的情况时，该结点即为环入口，返回该结点即可
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
long count=0;
while(twostep!=null && twostep.next!=null){
onestep=onestep.next;
twostep=twostep.next.next;
count++;
if(onestep==twostep){
while(true){
for(int i=0;i<count*2;i++){
onestep=onestep.next;
if(onestep==p){
return p;
}
}
p=p.next;
}
}
}
return null;
}
}```

## 题目描述

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

Can you solve it without using extra space?

## 解题思路

• 将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)

X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置。

2(a+b) = a+b+n*圆的周长 = a+b+n(b+c)

a = (n - 1) * b + n * c = (n - 1)(b + c) +c

## 代码提交

``````public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
//一快一慢两指针先找到相遇点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
//万一没有环的话直接直接返回Null了
if(fast == null || fast.next == null){
return null;
}
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}``````

class Solution {
public:
ListNode *detectCycle(ListNode *head) {

if(head == NULL || head -> next == NULL)
return NULL;

ListNode *slow = head, *fast = head;
//判断链表是否有环
while(fast && fast -> next){
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast) break;
}

if(slow != fast)
return NULL;

while(fast != slow){
slow = slow -> next;
fast = fast -> next;
}

return slow;
}
};

```/**
* 1->2->3->4->[5]->6
*       |__________|
* 找到慢指针low和快指针fast相遇的点（没相遇说明没环），
* low指针走过的长为a，fast走过的长为a+b+c，可得到等式：2a=a+b+c  =>a-c=b
*
* @return
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode low = head, fast = head;
while (fast != null && fast.next != null) {
low = low.next;
fast = fast.next.next;
if (low==fast){
while (fast!=low){
fast=fast.next;
low=low.next;
}
return low;
}
}
return null;
}
}
```

```/*
1.首先利用快慢指针判断链表中是否存在环，当快指针追上慢指针时，说明存在环，否则不存在.
2.计算环中的节点个数。在环中随意选一个节点并以此节点为起点开始遍历，当重复时便得到节点个数n。
3.找到环的入口。定义两个指针p1和p2，p1指向头节点，p2向后移动n步。随后使两个指针以相同的速度向后推进，两个指针重复的节点就是环的入口。
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
return nullptr;
ListNode *pointerFast = head->next;
ListNode *pointerSlow = head;
while(pointerFast != nullptr && pointerFast->next != nullptr && pointerFast != pointerSlow)
{
pointerFast = pointerFast->next->next;
pointerSlow = pointerSlow->next;
}
/*不存在环*/
if(pointerFast == nullptr || pointerFast->next == nullptr)
return nullptr;
/*存在环*/
else
{
/*让指针p1指向头节点，指针p2从头节点向后移动n（环中节点个数步）*/
ListNode *p1 = head;
ListNode *p2 = head->next;
pointerFast = pointerFast->next;
while(pointerSlow != pointerFast)
{
pointerFast = pointerFast->next;
p2 = p2->next;
}
/*让p1和p2以g相同的速度向前推进*/
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
}
};
```

class Solution {
//如果环内相遇，则可根据公式2(a+b)=a+b+nr(a代表起点到循环节点的距离,b代表相遇时，距循环
//节点的距离)，计算出此时应该有a = (n-1)r - b(系数n-1可以看做1)即将fast置于起点单步前行会和
//slow指针相遇
public:
ListNode *detectCycle(ListNode *head) {
return NULL;
ListNode *fast,*slow;
while(fast!=NULL && fast->next!=NULL)
{
slow = slow->next;
fast = fast->next->next;
//判断是否在环内相遇，若相遇则退出循环
if(slow == fast)
break;
}
//判断是否存在环，若不存在则直接返回NULL
if(fast==NULL || fast->next==NULL)
return NULL;
//将fast指针置于头结点，和slow指针同时单步遍历即会相遇在循环节点处
while(fast != slow)
{
slow = slow->next;
fast = fast->next;
}
return fast;
}
};

```//很烦，难道入口节点不应该是重复的吗，为什么是重复的前一个。
//我最初写了一个用ArrayList存储的，后来没办法换了快慢指针。我把两种方法都贴出来
//方法一：小众款，我的只能通过40%，有没有道友想用这种方法的可以帮在下一把吗
//方法二：大众款
import java.util.*;
public class Solution {
public ListNode detectCycle(ListNode head) {
return null;
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow)
break;
}
if(fast.next==null||fast.next.next==null)
return null;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}

```

1.快慢指针同时出发，如果快指针到达null，说明链表没有环
2.如果快慢指针相遇了，说明链表有环。
3.在快慢指针相遇的时候，让第二个慢指针从头结点出发，
4.当两个慢指针相遇的时候，相遇的位置就是环的起点。

0.假设链表有环，并且环之前的部分长n，环周长m，慢指针速度为1，快指针速度为2。环为顺时针
1.首先快指针和慢指针一起从F0S0出发。

2.快指针此时共走了2n的距离，在环上走了n的距离，

3.也就是说，当快指针追上慢指针的时候，慢指针从S1走了m-n%m到达S2F2。

4.快慢指针在S2F2相遇的时候，另一个慢指针2 从F0S0出发。

```class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *pSlow = head;
ListNode *pFast = head;
while(pFast&&pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next->next;
if(pFast==pSlow)
break;
}
if(!pFast||!pFast->next)
{//reach end
return nullptr;
}
else
{//loop
while(pSlow2 != pSlow)
{
pSlow2 = pSlow2->next;
pSlow = pSlow->next;
}
return pSlow2;
}
}
};
```

/****************************************************************************************************************

我的解法不同的地方在于对于循环的判断，比他的更加简单，不需要跳出循环来进行判断
******************************************************************************************************************/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
return NULL;
ListNode* runner = head;
ListNode* chaser = head;
while(runner!=NULL&&runner->next!=NULL){
runner = runner->next->next;
chaser = chaser->next;
if(runner == chaser) {
while(chaser!=runner){
chaser=chaser->next;
runner=runner->next;
}
return runner;
}//if
}//while
return NULL;
}
};

```public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode slow = head;
ListNode fast = head;
while(slow!=null && fast!=null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
//has cycle
ListNode p = head;
while(p!=slow){
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}

```

```public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode s = head;//定义慢指针
ListNode f = head;//定义快指针
return null;
while(f!=null&&f.next!=null)//快指针及其next不为空则快指针走两步，慢指针走一步
{
f = f.next.next;
s = s.next;
if(f==s)//两指针相等，说明有环并退出循环，慢指针保存相遇节点
break;
}
if(f==null||f.next==null)//若快指针或者他的next为空，说明无环
return null;
while(f!=s)//存在环时，快指针从头节点出发，慢指针从相遇节点出发，每次走一步，相遇节点即为环的入口节点
{
f = f.next;
s = s.next;
}
return s;
}
}```

138条回答 24226浏览

# 通过挑战的用户

• 2020-05-30 17:12:48
• 2020-05-30 16:43:53
• 2020-05-30 15:49:05
• 2020-05-30 10:59:26
• 2020-05-29 21:50:21

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题