[dai4] the entry node of the link in jz23 linked list

Title Description ：

reflection ：

Build a list, Storage nodes , Duplicate occurs , Just go back to .

class Solution:
    def EntryNodeOfLoop(self, pHead):
        if pHead is None or pHead.next is None:
            return None
        mem = []
        while pHead not in mem:
            mem.append(pHead)
            pHead = pHead.next
            if pHead is None:
                return None
        else:
            return pHead

answer ：

The answer is set(), Ratio of occupied memory list A lot less ; Remember to use more in the future set, It doesn't allow repetition

The space complexity required for the above answer is $O(n)$, Another answer is double pointer , The space complexity is $O(1)$
To solve the equation ~

Assume that the outer length of the ring is a, The inner length of the ring is b; Move the pointer two spaces at a time , The slow pointer moves one grid at a time ;

• Go to the entrance quickly ：$fast=a+n\ast b$;
• The speed pointer must meet in the ring , here $fast-slow=n\ast b$; Again because $fast=2\ast slow$, Substitute , When we met $slow=n\ast b$
• After encounter , Give Way fast Back to the head node , Slow the pointer and keep walking , When they meet again , It's the head node ;$slow=n\ast b+a$, It happens to meet the fast node at the entrance .

It took me a long time to understand , This is too clever

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow = pHead
        fast = pHead
        while fast !=None and fast.next !=None:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                while pHead != slow:
                    pHead =pHead.next
                    slow = slow.next
                return slow
        return None