LeetCode141.环形链表

**环形链表**

环形链表是一种特殊类型的链表，它们的最后一个结点指向第一个结点，从而形成一个环。这种结构使得链表可以在有限的空间内存储大量的数据。

**问题描述**

给定一个环形链表，找到入口结点（也就是环开始的地方）。

**示例**

输入：1 ->2 ->3 ->4 ->5 ->2输出：2**解决方案**

我们可以使用哈希表来存储每个结点的值和对应的下一个结点的值。然后，我们可以遍历链表，直到找到重复的值，这个值就是环开始的地方。

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef hasCycle(head):
 """
 :type head: ListNode :rtype: bool """
 if not head or not head.next:
 return False slow = fast = head while fast and fast.next:
 slow = slow.next fast = fast.next.next # If the fast pointer catches up to the slow pointer,
 # it means there is a cycle in the linked list.
 if slow == fast:
 return True return Falsedef detectCycle(head):
 """
 :type head: ListNode :rtype: ListNode """
 if not hasCycle(head):
 return None slow = head while True:
 slow = slow.next # When the fast pointer catches up to the slow pointer,
 # it means we have found the start of the cycle.
 fast = head while fast != slow:
 fast = fast.next return slow# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = head # Create a cycleprint(detectCycle(head).val) # Output:2

**注释**

* `hasCycle` 函数用于检测链表是否有环。它使用两个指针（慢速和快速）来遍历链表。如果快指针在链表中移动两步时，遇到一个结点，而慢指针只移动一步，那么这意味着链表有环。
* `detectCycle` 函数用于找到环的起始位置。它首先使用 `hasCycle` 函数来检测是否存在环。如果没有环，则返回 None。如果存在环，它会将慢速指针置于链表头部，然后再次使用快指针和慢指针来找到环的起始位置。

**时间复杂度**

* `hasCycle` 函数的时间复杂度为 O(n)，其中 n 是链表中的结点数。
* `detectCycle` 函数的时间复杂度也为 O(n)。

**空间复杂度**

* `hasCycle` 和 `detectCycle` 函数都使用常数大小的额外空间，因此它们的空间复杂度均为 O(1)。