判断链表中的环Floyd

问题源于 leetcode 中的一道题:
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
就比方说下面这个图，就是返回那个红色的点

链表的数据结构：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

算法介绍

• 先定义两个指针，一个叫 fast，一个叫 slow，都指向链表中的第一个节点，
• fast 一次向前走两步(fast = fast.next.next)，slow 一次走一步 (slow = slow.next)
• 如果这个链表中有环，那 slow 和 fast 一定会在环中的某处相遇
• 记录 slow 走过的路程为 x ，那么 fast 走过的路程就是 2x，即为 slow 再走 x 就能回到自己的位置
• 再把 x 分成 y + z ，y 表示从起始点到红点的路程，z 表示从红点到相遇点 slow 走过的路程，z 不好在图中表示

• 然后就得出了这样一个结论：slow 如果在相遇点处，再走个 y + z 就可以再回到这个相遇点处，slow 如果在红点处，走个 z 就能到相遇点处。一定要理解这句话
• 根据上面这个结论，可以得出：1. slow 在相遇点处，再走个 y 就能到红点处。2. 再往链表的起始点处创一个指针 slow2，则这个指针走 y 的路程，可到达红点处
• 让 slow2 和 slow 同时开始走(slow2 = slow2.next; slow = slow.next;)， 它们相遇的地方，就是红点

算法代码

public class Solution {
            //这里给出的是链表的头节点
            public ListNode detectCycle(ListNode head) {
                ListNode slow = head;
                ListNode fast = head;
                while (fast!=null && fast.next!=null){
                    fast = fast.next.next;
                    slow = slow.next;
                    
                    if (fast == slow){
                        ListNode slow2 = head; 
                        while (slow2 != slow){
                            slow = slow.next;
                            slow2 = slow2.next;
                        }
                        return slow;
                    }
                }
                return null;
            }
        }

源代码出自:https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation.