环形链表 II
题目要求
这个问题要求我们确定一个给定链表是否有环，如果有环，需要返回环的起始节点。如果没有环，则返回 null。链表的环是指链表中的一个节点的 next 指针指向链表中的一个先前的节点，这样就形成了一个环。题目中提到的pos变量是用来表示链表中环的起始位置的索引，但这个值在实际的函数实现中并不会给出，它只是用来说明问题。
解题思路
解决这个问题的一个经典方法是使用快慢指针（Floyd 的循环检测算法）。以下是解题的步骤：
-
初始化两个指针，快指针
fast和慢指针slow，它们都指向链表的头节点head。 -
移动这两个指针，
slow指针每次移动一个节点，fast指针每次移动两个节点。如果链表中没有环，那么fast指针最终会遇到 null，这时我们可以返回 null。 -
如果链表中有环，那么
fast指针最终会追上slow指针（因为每次循环fast比slow多走一步，如果有环它们最终会在环内相遇）。 -
当
fast和slow相遇时，将fast（或slow）指针重新指向头节点head，然后fast和slow都每次移动一个节点，当它们再次相遇时，相遇点就是环的起始节点。 -
返回相遇点，即为环的起始节点。
这个算法的关键在于第 4 步。当两个指针在环内相遇后，我们为什么要将其中一个指针重新指向头节点，然后两个指针都以相同的速度移动？这是因为从头节点到环起点的距离和从相遇点到环起点的距离是相等的。这个结论可以通过数学证明得到，是解决这类问题的关键。
设：
- 链表起点到环起点的距离为 \( D \)。
- 环起点到快慢指针相遇点的距离为 \( S_1 \)。
- 相遇点回到环起点的距离为 \( S_2 \)。
当快慢指针在环内相遇时：
- 慢指针走过的总距离为 \( D + S_1 \)。
- 快指针走过的总距离为 \( D + S_1 + S_2 + S_1 \)，因为它已经在环里至少走了一圈才遇到慢指针。
由于快指针的速度是慢指针的两倍，我们可以得出以下等式：
\[ 2(D + S_1) = D + 2S_1 + S_2 \]
通过简化上述等式，我们得到：
\[ 2D + 2S_1 = D + 2S_1 + S_2 \]
\[ 2D + 2S_1 - 2S_1 = D + S_2 \]
\[ 2D = D + S_2 \]
从而：
\[ D = S_2 \]
这意味着从链表起点到环起点的距离 \( D \) 等于从相遇点回到环起点的距离 \( S_2 \)。
因此，如果我们将一个指针重新放回链表的起始点，而另一个指针保持在相遇点，然后两个指针都以相同的速度前进，那么：
- 当第一个指针从链表起点走到环起点时，它走过了距离 \( D \)。
- 同时，第二个指针从相遇点出发，也走过了距离 \( S_2 \)。
由于 \( D = S_2 \)，两个指针将会在环的起点相遇。这就证明了当两个指针再次相遇时，它们一定是在环的起始点相遇。
Golang 版本
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
slow := head
fast := head
hasCycle := false
// 快慢指针判断是否有环
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
hasCycle = true
break
}
}
// 如果有环，找到环的入口
if hasCycle {
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
return nil
}
这段代码定义了一个ListNode结构体，用于表示链表节点。detectCycle函数用于检测链表中是否存在环，并返回环的起始节点。如果不存在环，则返回nil。函数中首先对链表进行了空检查，然后使用快慢指针的方法来检测环，并在确认链表中存在环后找到并返回环的起始节点。
C++版本
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
ListNode *slow = head;
ListNode *fast = head;
bool hasCycle = false;
// 使用快慢指针检测环
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
hasCycle = true;
break;
}
}
// 如果存在环，找到环的入口
if (hasCycle) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
return nullptr;
}
};
这段 C++代码定义了一个ListNode结构体和一个Solution类。Solution类中的detectCycle成员函数用于检测链表中是否存在环，并返回环的起始节点。如果不存在环，则返回nullptr。函数中首先对链表进行了空检查，然后使用快慢指针的方法来检测环，并在确认链表中存在环后找到并返回环的起始节点。
Python 版本
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
has_cycle = False
# 使用快慢指针检测环
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
# 如果存在环，找到环的入口
if has_cycle:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
这段 Python 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类。Solution类中的detectCycle方法用于检测链表中是否存在环，并返回环的起始节点。如果不存在环，则返回None。方法中首先使用快慢指针的方法来检测环，并在确认链表中存在环后找到并返回环的起始节点。
Java 版本
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 slow = head;
ListNode fast = head;
boolean hasCycle = false;
// 使用快慢指针检测环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
// 如果存在环，找到环的入口
if (hasCycle) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
return null;
}
}
这段 Java 代码定义了一个ListNode类用于表示链表节点，以及一个Solution类。Solution类中的detectCycle方法用于检测链表中是否存在环，并返回环的起始节点。如果不存在环，则返回null。方法中首先使用快慢指针的方法来检测环，并在确认链表中存在环后找到并返回环的起始节点。
Rust 版本
#![allow(unused)] fn main() { use std::rc::Rc; use std::cell::RefCell; // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Rc<RefCell<ListNode>>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val, } } } pub struct Solution; impl Solution { pub fn detect_cycle(head: Option<Rc<RefCell<ListNode>>>) -> Option<Rc<RefCell<ListNode>>> { let (mut slow, mut fast) = (head.clone(), head); while let Some(fast_node) = fast { slow = slow.unwrap().borrow().next.clone(); fast = fast_node.borrow().next.clone().and_then(|next| next.borrow().next.clone()); if Rc::ptr_eq(&slow.as_ref()?, &fast.as_ref()?) { let mut ptr = head; while !Rc::ptr_eq(&slow.as_ref()?, &ptr.as_ref()?) { slow = slow.unwrap().borrow().next.clone(); ptr = ptr.unwrap().borrow().next.clone(); } return ptr; } } None } } }
这段 Rust 代码定义了一个ListNode结构体用于表示链表节点，以及一个Solution结构体。Solution结构体中的detect_cycle方法用于检测链表中是否存在环，并返回环的起始节点。如果不存在环，则返回None。方法中首先使用快慢指针的方法来检测环，并在确认链表中存在环后找到并返回环的起始节点。在 Rust 中，链表节点通常使用Rc<RefCell<T>>来允许多个所有者和可变借用。
总结
上面给出的解法使用了快慢指针的方法来检测链表中是否存在环，并找到环的起始节点。这种方法在多种编程语言中都可以很好地实现。具体步骤包括：
- 初始化两个指针，一个慢指针和一个快指针，它们都指向链表的头节点。
- 使用快慢指针的方法来检测链表中是否存在环。如果存在环，快指针最终会追上慢指针。
- 如果存在环，将其中一个指针重新指向头节点，然后两个指针都以相同的速度移动。它们再次相遇的地方就是环的起始节点。
这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，是一种高效的解决链表环问题的方法。