Leetcode 142. Linked List Cycle II 题目解析与答案

首先，我们需要理解这个问题的本质。给定一个链表，我们需要判断它是否有循环，并返回循环的起始节点。这个问题可以通过Floyd的循环查找算法（也称为“乌龟和兔子”算法）来解决。
Floyd的循环查找算法使用了两个指针，一个快指针和一个慢指针。快指针每次移动两步，慢指针每次移动一步。如果链表中存在循环，那么快指针和慢指针最终会在某个节点上相遇。一旦它们相遇，我们可以重新设置慢指针为链表的头节点，然后同时以相同的速度移动两个指针。当它们再次相遇时，相遇点就是循环的起始节点。
下面是一个Python的实现示例：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def detectCycle(head):
slow = head
fast = head
# 判断是否存在循环
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
# 如果不存在循环，返回None
return None
# 找到循环的起始节点
ptr1 = head
ptr2 = slow
while ptr2 != ptr1:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1

在这个实现中，我们首先创建了两个指针，slow和fast，并将它们都设置为链表的头节点。然后，我们进入一个循环，在每个循环迭代中，slow指针移动一步，而fast指针移动两步。如果链表中存在循环，slow和fast指针最终会在某个节点上相遇。一旦它们相遇，我们就退出循环。然后，我们重新设置slow指针为链表的头节点，并同时移动slow和fast指针，直到它们再次相遇。相遇点就是循环的起始节点。如果链表中不存在循环，那么fast指针将到达链表的末尾，此时我们可以返回None。
这个算法的时间复杂度是O(n)，其中n是链表的长度。这是因为无论是存在循环还是不存在循环，我们都需要遍历整个链表一次。空间复杂度是O(1)，因为我们只使用了常数额外空间。