Linked List Cycle Problems - Given a linked list, return to the first node of the linked list that begins to enter the ring

Linked List Cycle Problems - Given a linked list, return to the first node of the linked list that begins to enter the ring

Topic description:
Given a linked list, return to the first node of the linked list that begins to enter the ring. If the linked list has no rings, it returns null.
In order to represent the rings in a given linked list, we use the integer pos to indicate the position where the tail of the linked list is connected to the linked list (the index starts at 0). If pos is -1, there is no ring in the list.
Note: It is not allowed to modify the given linked list.


Formula calculation:
It is easy to get:
m=x+y (two representations of the length of the ring); the
fast pointer takes two steps and the slow pointer takes one step. So the speed of the fast pointer is twice the speed of the slow pointer, so in the same time, the length of the fast pointer is twice the length of the slow pointer:
yes: f=2s;
after the fast pointer walks through the circle, the two pointers meet , There is: m+kn+y=2(m+y);
after removing the brackets there is: m+kn=2m+y;
solved: m=kn-y;
and because: n=x+y;
so there are: m=kn-(nx);
Therefore: m=x+n(k-1).
m is the length from the head node to the beginning of the ring;
x is the length from the meeting point to the head node;
xm is the length of (k-1) rings.
Through the calculation of the formula, we can understand that
after finding the meeting point, the head node of the linked list and the meeting point node start at the same time, and the meeting point is the starting point of the ring. The node at the meeting point walked (k-1) more rings.

/**
 * 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) {
        if(head==null)
            return null;
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        if(fast == null || fast.next == null)
            return null;
        fast = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
Explanation of the code:
1. If head is empty, there is no ring, and directly returns null;
2. Set the start of the fast and slow pointers to point to the head, set the loop condition, the fast pointer is not empty and the next field of the fast pointer points to not air enters a loop in which a null pointer pointing to the next field is not null pointer can take two steps to ensure fast, or there may be a null pointer exception;
3, if the speed of the pointer to the same node, then the break off point is met;
4, After the first loop, if fast is empty or fast.next is empty, there is no ring and returns null;
5. If there is a ring, let the fast pointer move from the beginning, the slow pointer moves from the point of encounter, and the encounter is the starting point, Just return it.