牛客网高频算法题系列-BM7-链表中环的入口节点

牛客网高频算法题系列-BM7-链表的入口节点，请找到链表环的入口节点，否则返回null。见原标题：BM7链表中环的入口节点的解法一：双指针法用的是fast和slow两个指针。它们都从链表的头部开始。随后，慢指针一次向后移动一个位置，而快指针向后移动两个位置。如果链表中存在环路，那么快指针最终会在环中再次遇到慢指针。如果相遇，则相遇到入口节点的距离与头节点到入口节点的距离相同。所以resetfast为头节点，fast和sow节点会一步步走，直到相遇，就是入口节点。原理可参考：双指针算法原理详解解法二：Hash方法使用HashSet记录链表中的节点，然后遍历链表节点：如果链表中的节点出现在哈希表，表示链表是有环的，这个节点是入口节点。如果链表中的节点还没有出现在哈希表中，则将当前节点添加到哈希表中，然后判断下一个节点。最后，如果没有重复节点，则表示没有循环，返回null。说明：与牛客网高频算法题系列-BM6-判断链表是否有环基本相同。代码导入java.util.HashSet；publicclassBm007{/***双指针**@parampHead*@return*/publicstaticListNodeentryNodeOfLoop(ListNodepHead){ListNodefast=pHead,slow=pHead;while(fast!=null&&fast.next!=null){//快指针每次移动2步，慢指针每次移动1步fast=fast.next.next;慢=慢.next;if(fast==slow){//fast和slow指针相遇，说明链表有环break;}}//如果快指针为null，说明快慢指针没有相遇，不环，returnnullif(fast==null||fast.next==null){returnnull;}快速=pHead;//以与第一个遇到的节点相同的速度开始，遇到的节点为入口节点while(fast!=slow){fast=fast.next;慢=慢.next;}//fast和slow指针不满足，说明非循环返回fast；}/***Hashmethod**@parampHead*@return*/publicstaticListNodeentryNodeOfLoop2(ListNodepHead){//用来记录链表中的节点HashSetnodes=newHashSet<>();while(pHead!=null){//如果链表中的节点已经出现，则该节点为环的入口，returnif(nodes.contains(pHead)){returnpHead;}nodes.add(pHead);pHead=pHead.next;}返回空值；}publicstaticvoidmain(String[]args){/***测试用例的链表结构是循环的*testCaseCycle:3->2->0->-4*^|*----------*/ListNodehead=ListNode.testCaseCycle();/***测试用例，预期输出：2*/System.out.println(entryNodeOfLoop(head));System.out.println(entryNodeOfLoop2(head));}}$1.01^{365}≈37.7834343329$$0.99^{365}≈0.02551796445$相信坚持的力量！