Linked list: the entry node of the link in the linked list

Their thinking

According to the meaning , First of all, we have to judge whether there is a ring in the linked list .
secondly , According to the characteristics of the ring , We define Fast slow double pointer , Move forward , There must be a time to meet , meet The node of is exactly the entry node of the link in the linked list .
A two-step ：

1. Find the number of nodes in the ring .

• Define double pointer , The previous pointer takes two steps first , The back pointer takes one step , Both pointers continue to move forward at the same time , If the list has links , Then the two pointers must meet , Return to one Nodes in the ring k
• According to the properties of the ring , Along nodes k Move forward , Because there are rings , So the pointer will go back to k node , This process of exploration leads to Number of nodes in the ring N.

2. Find the node where the two pointers meet in the ring

• Define fast and slow double pointers ,
• Let's go first N Step .
• Slow pointer , Quick pointer , Moving forward at the same time . When two pointers are equal , Then meet , Return to the encounter node .

Code

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
       ListNode inLoop = getNodeInLoop(head);
       if(inLoop == null) {
    
           return null; //  Determine if the list has links .
       }
       int loopCount = 1;
       for(ListNode node = inLoop; node.next != inLoop; node = node.next){
    
           loopCount++; // Count the number of nodes in the ring .
       }

        ListNode fast = head;
        ListNode slow = head;
       for(int i = loopCount; i > 0; i--) {
    
           fast = fast.next;
       }
       while(slow != fast) {
    
           slow = slow.next;
           fast = fast.next;
       }

       return slow;
    }

    private ListNode getNodeInLoop(ListNode head) {
    
        if(head == null || head.next ==null) {
    
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
    
            if(slow == fast) {
    
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
            if(fast != null) {
    
                fast = fast.next;
            }
        }
         return null;
    }
}

summary

This topic examines the characteristics of linked lists , That is, how to find whether there are links in the linked list through the fast and slow pointers , Returns the entry node of the ring .