题解 | #链表中环的入口结点#

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
'''class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        links = []
        p = pHead
        while p:
            if p in links:
                return p
            else:
                links.append(p)
            p = p.next'''
            
# 双指针法
class Solution:
    def EntryNodeOfLoop(self, pHead):
        slow = pHead # 每次走一步
        fast = pHead # 每次走两步
        #count = 0
        while (fast and fast.next):
            #count += 1
            slow = slow.next
            fast = fast.next.next
            if (slow == fast): # 确认有循环
                break
        #print(slow.val)
        if (not fast or not fast.next): # 可能是{1，2}， {}无循环
            return None
        # 如果有环，fast和slow一定会相遇，比如对用例{1，2} {3,4,5,6}
        # fast 和 slow相遇的时候，分别走了8步和4步，起点到入口的距离是X，slow走了S步，它距入口3的
        # 距离为S-X，另一半圆2*S - X-(S-X)*2=X,所以我们将fast置于起点，slow继续走完另一半圆，他们
        # 会在入口相遇
        fast = pHead
        while(fast != slow):
            slow = slow.next
            fast = fast.next
        return fast