本文主要是介绍BM7 链表中环的入口结点（快慢指针模板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围： 𝑛≤10000n≤10000，1<=结点值<=100001<=结点值<=10000
要求：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1
输入：{1,2},{3,4,5}
输出：3示例2
输入：{1},{}
输出："null"示例3
输入：{},{2}
输出：2思路：建立在上一道基础上，如果已知成环，慢指针移动到链表头部，快慢指针以1的步长去移动，直到两者相遇，有环必相遇。
package com.niuke;public class BM7 {public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode slow = pHead;ListNode fast = pHead;boolean flag = false;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if (slow == fast){//说明是有环的flag = true;break;}}if (flag){//说明有环slow = pHead;while (slow != fast){slow = slow.next;fast = fast.next;}return slow;}return null;}static class ListNode{int val;ListNode next;public ListNode(int x){this.val = x;next = null;}// TODO: 2024-05-12 完成代码}
}
这篇关于BM7 链表中环的入口结点（快慢指针模板题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
