[142][中等][双指针] 环形链表 II

题目描述

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