题目描述
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：
解题思路
依旧是快慢指针.
如果有环, 假设在快慢指针相遇时, 慢指针走了k步, 快指针走了2k步. 设相遇点距环的起点的距离为m, 那么环的起点距离头结点的距离为k−m, 而且快指针已经走完了一圈环, 抛开覆盖的慢指针走过的路, 以及覆盖的两者都走过的环起点到相遇点的路长m, 则相遇点到环起点的距离也为k−m.
因此在相遇后, 将其中一个指针重新放置在头节点处, 两个指针再次相遇时, 就是在环起点的位置, 计数走的步数, 就是最终的结果.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
