[数据结构与算法]剑指Offer 23. 链表中环的入口节点

题目描述：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
输入说明：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表。
示例1：

输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3   

示例2：

输入：{1},{}
返回值："null"
说明：没有环，返回null，后台打印"null" 

示例3：

输入：{},{2}
返回值：2
说明：只有环形链表节点2，返回节点2，后台打印2   

方法一：
分析：1.判断是否有环，如果没有环，返回null，如果有环，则快慢指针一定会相遇，且在环中相遇，记录在环中相遇的节点。2.从该相遇节点开始，一边移动，一边计数，当下一次到达该节点时，就可以求得环中的节点数x。3.最后将快慢指针同时置于开始节点，快指针先走x步，接着快慢指针同时一步一步移动，下一次相遇时，就是环的入口节点。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 判断是否存在环
        ListNode node = MeetingNode(pHead);
        if (node == null) {
            return node; // 没有环
        }
        
        // 有环，则node就是快慢指针在环中相遇的节点
        int count = 1;
        ListNode nextNode = node.next;
        while (node != nextNode) {
            nextNode = nextNode.next;
            count++;
        }
        // 循环结束后，count的值就是环的长度
        
        ListNode fast = pHead;
        ListNode slow = pHead;
        // fast先走count步
        int i = 0;
        while (i < count) {
            fast = fast.next;
            i++;
        }
        // 然后二者再同时向后一次移动一步，再次相遇的节点就是入环节
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast; // 返回slow也可以，此时fast和slow指向同一个节点
        
    }
    
    // 判断是否有环，如果无环，返回null，如果有环，返回在环中相遇的节点
    public ListNode MeetingNode(ListNode pHead) {
        // 如果没有环，返回null
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode fast = pHead; // 快指针，一次走两步
        ListNode slow = pHead; // 慢指针，一次走一步
        do {
            fast = fast.next.next;
            slow = slow.next;
        } while(fast != slow && fast != null && fast.next != null);
        if (fast == null || fast.next == null) {
            return null; // 没有环
        }
        return fast; // 返回slow也可以，此时二者指向同一个节点
    }
}

时间复杂度：$O(n)$，空间复杂度：$O(1)$。

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。