142. 环形链表 II(中)

• 题目
• 题解：双指针

题目

• 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
  不允许修改 链表。

题解：双指针

• 慢指针走一步，快指针走两步，若有环，当快指针追上慢指针时，让慢指针回到头，两指针一起走，相遇的点就是入环的第一个点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        left=head
        right = head
        if not head or not head.next:# 空链表或只有一个节点，肯定没有环
            return None
        while right and right.next:
            left=left.next
            right=right.next.next
            if right==left:
                break
        if left!=right:# 快指针到达链表末尾，没有环
            return None
        left=head#让慢指针回到头
        while left!=right:#两指针一起走，相遇的点就是入环的第一个点
            left=left.next
            right=right.next
        return left