Sword finger offer II 022 The entry node of the link in the linked list

subject ： Given a linked list , Return to the first node of the link where the list begins to enter . Start from the head node of the linked list next The first node where the pointer enters the ring is the entry node of the ring . If the list has no links , Then return to null.

Answer key ： Use the speed pointer to determine whether there is a ring , When there is a ring, quickly return the pointer to the chain header , Then the two pointers move one step at the same time , It is the entry node when they meet again

Official explanation

Code

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
class Solution {
    
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
    
        ListNode* fast = pHead, *slow = pHead, *ptr = pHead;
        
        while (NULL != fast) {
    
            if (NULL == fast->next) {
    
                break;
            }
            
            slow = slow->next;
            fast = fast->next->next;
            
            if(slow == fast) {
    
                while (ptr != slow) {
    
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        
        return NULL;
    }
};