python3题解 -快慢指针| #链表中环的入口结点#

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead:ListNode):
        # write code here
        slow = self.hasCycle(pHead)
        if not slow: return None
        fast = pHead
        while fast !=slow:
            slow = slow.next
            fast = fast.next
        return slow

    def hasCycle(self, head):
        if not head:return None
        fast = head
        slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return slow
        return None
# class Solution:
#     # 判断有没有环，返回相遇的地方
#     def EntryNodeOfLoop(self, pHead: ListNode):
#         slow = self.hasCycle(pHead)
#         # 没有环
#         if slow == None:
#             return None
#         # 快指针回到表头
#         fast = pHead
#         # 再次相遇即是环入口
#         while fast != slow:
#             fast = fast.next
#             slow = slow.next
#         return slow

#     def hasCycle(self, head):
#         # 先判断链表为空的情况
#         if head == None:
#             return None
#         # 快慢双指针
#         fast = head
#         slow = head
#         # 如果没环快指针会先到链表尾
#         while fast != None and fast.next != None:
#             # 快指针移动两步
#             fast = fast.next.next
#             # 慢指针移动一步
#             slow = slow.next
#             # 相遇则有环
#             if fast == slow:
#                 # 返回相遇的地方
#                 return slow
#         # 到末尾则没有环
#         return None