牛客网高频算法题系列-BM7-链表中环的入口结点
题目形容
给一个长度为n链表，若其中蕴含环，请找出该链表的环的入口结点，否则，返回null。
原题目见：BM7 链表中环的入口结点
解法一：双指针法
应用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后挪动一个地位，而fast 指针向后挪动两个地位。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
如果相遇了，从相遇处到入口结点的间隔与头结点与入口结点的间隔雷同。所以将fast从新设置为头结点，fast和sow结点都一步步走，直到相遇，即为入口结点。
原理可参考：双指针算法原理详解
解法二：哈希法
应用HashSet记录链表中的结点，而后遍历链表结点：
- 如果链表中的结点在哈希表中呈现过，阐明链表有环，并且该结点即为入口结点，返回之
- 如果链表中的结点没有在哈希表中呈现过，则将以后结点增加到哈希表中，而后判断下一个结点
最初，如果没有反复节点，则阐明无环，返回null。
阐明：和 牛客网高频算法题系列-BM6-判断链表中是否有环 的解法基本一致。
代码
import java.util.HashSet;public class Bm007 { /** * 双指针 * * @param pHead * @return */ public static ListNode entryNodeOfLoop(ListNode pHead) { ListNode fast = pHead, slow = pHead; while (fast != null && fast.next != null) { // 快指针每次走2步，慢指针每次走1步 fast = fast.next.next; slow = slow.next; if (fast == slow) { // 快慢指针相遇，阐明链表中有环 break; } } // 如果快指针为null，阐明快慢指针没有相遇，无环，返回null if (fast == null || fast.next == null) { return null; } fast = pHead; // 与第一次相遇的结点雷同速度登程，相遇结点为入口结点 while (fast != slow) { fast = fast.next; slow = slow.next; } // 快慢指针没有相遇，阐明无环 return fast; } /** * 哈希法 * * @param pHead * @return */ public static ListNode entryNodeOfLoop2(ListNode pHead) { // 用来记录链表中的结点 HashSet<ListNode> nodes = new HashSet<>(); while (pHead != null) { // 如果链表中的结点曾经呈现过，这个结点即为环的入口，返回之 if (nodes.contains(pHead)) { return pHead; } nodes.add(pHead); pHead = pHead.next; } return null; } public static void main(String[] args) { /** * 测试用例链表构造为有环 * testCaseCycle： 3 -> 2 -> 0 -> -4 * ^ | * ------------ */ ListNode head = ListNode.testCaseCycle(); /** * 测试用例，冀望输入： 2 */ System.out.println(entryNodeOfLoop(head)); System.out.println(entryNodeOfLoop2(head)); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！