[LeetCode] 142. Linked List Cycle II 链表中的环 II

2021年09月15日 阅读数：3

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

Can you solve it without using extra space?java

Java：post

```public class Solution {
public ListNode detectCycle( ListNode head ) {
return null;
}
// 快指针fp和慢指针sp，
while( fp != null && fp.next != null){
sp = sp.next;
fp = fp.next.next;
//此处应该用fp == sp ，而不能用fp.equals(sp) 由于链表为1 2 的时候容易
//抛出异常
if( fp == sp ){  //说明有环
break;
}
}
//System.out.println( fp.val + "   "+ sp.val );
if( fp == null || fp.next == null ){
return null;
}
//说明有环，求环的起始节点
while( fp != sp ){
sp = sp.next;
fp = fp.next;
}
return sp;
}
} 　　```

Python：url

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def __str__(self):
if self:
return "{}".format(self.val)
else:
return None

class Solution:
# @return a list node
while fast and fast.next:
fast, slow = fast.next.next, slow.next
if fast is slow:
while fast is not slow:
fast, slow = fast.next, slow.next
return fast
return None　　```

C++：spa

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