day5-环形链表II

**Day5: 环形链表 II**

在前面的章节中，我们已经学习了如何检测一个链表是否为环形链表。然而，这个问题的难度还不够高，今天我们要解决的是环形链表 II 的问题。

###问题描述给定一个链表的头节点 `head`，其中包含 `n` 个元素。请你判断链表中是否存在环，并且找到这个环的起始点。如果链表中没有环，则返回 `null`。

假设链表中有一个环，这个环的起始点是第一个进入环的结点。如果链表中没有环，则认为整个链表都是直线的，没有环。

### 解决方案为了解决这个问题，我们可以使用两个指针来检测环形链表。我们将快指针 `fast` 和慢指针 `slow` 都设置为链表的头节点 `head`。然后，我们让快指针每次移动两步，而慢指针每次移动一步。如果链表中存在环，那么快指针和慢指针一定会相遇。

当快指针和慢指针相遇时，我们将快指针重新设置为链表的头节点 `head`，然后让快指针和慢指针都移动一步。再次，当快指针和慢指针相遇时，这个点就是环形链表的起始点。

###代码实现

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef detectCycle(head):
 """
 :type head: ListNode :rtype: ListNode """
 # 检测环形链表 if not head or not head.next:
 return None slow = fast = head while fast and fast.next:
 slow = slow.next # 慢指针每次移动一步 fast = fast.next.next # 快指针每次移动两步 if slow == fast: # 如果快指针和慢指针相遇，则存在环形链表 break # 检测环形链表的起始点 if not (slow and fast):
 return None slow = head # 快指针重新设置为头节点 while slow != fast: # 慢指针和快指针都移动一步，直到相遇 slow = slow.next fast = fast.next return slow# 测试用例head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

head.next = node2node2.next = node3node3.next = node4node4.next = node2 # 环形链表print(detectCycle(head).val) # 输出:2