Entry node of link in linked list - linked list topic

sketch ：
The main requirement of the topic is a linked list with links （ There is no need to prove whether there is a ring ）, We need to find the specific node of the linked list as the entry node , For example, above 345 Is a ring node ,3 Is the ring inlet , So we just have to find a way to get 3 This node .
First
My main solution to this problem is （ There is no need to know the solution of the number of nodes in the ring ）, Algorithm problems must first be conceived in your mind , What are the specific steps . First, let's briefly talk about how to solve this problem by knowing the number of nodes in the ring , This is simpler , This is the solution that many people should first think of .

It is still the conventional double pointer solution , First step , Set speed pointer ,P1 For fast pointer ,P2 For slow pointer , Let them all point to the head node . In the second step, we need to find the number of nodes in the link in the list （N）, Then go ahead N Step . The third step , The fast pointer and the slow pointer move forward at the same speed , When the fast pointer and the slow pointer meet , The node that meets is the entry node of the ring .（ The following is an example ）

Next, we mainly introduce the solution without knowing the number of nodes in the ring . Although the above solution is easy to think of , But the amount of code is actually quite a lot , First, you need to find the number of nodes in the ring, and then find the meeting node in the double pointer . If you analyze it carefully , You will find that it is not necessary to find the number of nodes in the ring . Set the fast pointer to take two steps at a time , Slow pointer one step at a time , If there are links in the list , The fast and slow pointers must meet at a node in the ring , We can assume a special case to analyze the whole process （ The fast pointer only circulates once in the ring and encounters the slow pointer ）, Let the distance from the starting point to the entrance of the ring be X, The entrance from the meeting point to the ring is Y, The distance of one circle of the ring is C, So the distance that the slow pointer goes is X+C-Y, The distance traveled by the fast pointer is X+C+C-Y, And because the speed of the fast pointer is twice that of the slow pointer , So you can get 2（X+C-Y）=X+C+C-Y. After simplification , It can be concluded that X=Y, That is, the distance from the starting point to the entrance of the ring must be equal to the distance from the meeting point to the entrance of the ring , With this conclusion, all the problems were solved , After the fast and slow pointers meet , We just need to set another pointer to the starting point , Then let the slow pointer at the meeting point and the starting point pointer move forward at the same speed , When the starting point pointer meets the slow pointer , The meeting point is the entrance of the ring .

Post code

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
    

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    
         if(pHead==null||pHead.next==null)// Determine whether the linked list exists and under special circumstances 
        {
    
            return null;
        }
        ListNode fast=pHead;// Quick pointer 
        ListNode slow=pHead;// Slow pointer 
        while(fast!=null&&fast.next!=null){
    
            fast=fast.next.next;// Go two steps at a time 
            slow=slow.next;// Slow pointer one step at a time 
            if(fast==slow){
    
                ListNode slow2=pHead; Start point pointer 
               while(slow2!=slow){
      // Judge whether the start pointer meets the slow pointer , The meeting point is the entry point of the ring 
                   slow2=slow2.next;
                   slow=slow.next;
               }
               return slow2;
            }
        }
        return null;
    }
}