[数据结构与算法]一分钟解决数据结构问题-----链表开始入环的第一个节点

此题为力扣链表题目：

📌 文章目录：

1??.题目解析

2??.代码实现

3??.全部代码

题目：

1??.题目解析

此题需要得到链表环的入口第一个结点，如果没有环返回空，该题需要推导一个公式：即链表到环的入口距离和相遇点到环的距离一致

极端条件：

一般情况：

所以可以得出结论只要找到相遇的位置，相遇位置和链表的起始位置，同时走，当两个结点相遇时，即环的入口的第一个结点

2??.代码实现

步骤一、判断链表为不为空

if (head == null){
            return null;
        }

步骤二、找到相遇的结点

ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                break;
            }
        }

步骤三、如果循环是因为如下条件终止的，证明链表中没有环，返回 null

if(fast == null || fast.next == null){
            return null;
        }

步骤四、相遇结点和头结点同时走，直到相遇

while(cur != fast){
            cur = cur.next;
            fast = fast.next;
        }

步骤五、返回相遇的结点即是环的入口

return cur;

3??.全部代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        //判断有没有环
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                break;
            }
        }
        //没有环
        if(fast == null || fast.next == null){
            return null;
        }
        while(cur != fast){
            cur = cur.next;
            fast = fast.next;
        }
        return cur;
    }
}