本文共 1811 字，大约阅读时间需要 6 分钟。

目录

一、问题描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

二、代码实现

1、哈希法

循环遍历单链表的每个节点，

    如果当前节点的地址出现在set中，则说明它是环的入口节点，直接返回

    如果没有出现在set中，则将其添加到set中

当退出循环，说明链表不存在环，返回null（如果存在，在循环中就应该返回了）

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/import java.util.HashSet;public class Solution {        //哈希法    public ListNode EntryNodeOfLoop(ListNode pHead) {        HashSet
   
     set = new HashSet<>();        while (pHead != null) {            if (set.contains(pHead)) {                return pHead;            }                        set.add(pHead);            pHead = pHead.next;        }        return null;    }}
   

2、双指针法

第一步，让快慢指针均指向头节点，然后fast指针一次走两步，slow指针一次走一步。如果期间fast变为null或者fast.next变为null，说明链表不存在环，直接返回null。如果期间存在fast == slow，说明链表存在环，并记此时的节点为快慢指针第一次相遇的节点p。

第二步，让slow指针重新指向头节点、fast原地不动，然后让slow指针、fast指针每次走一步，则它们再次相遇的地方，就是环的入口节点q。

证明：在第一步中，由于快指针的速度是慢指针的两倍，并且它们在p点相遇，则2(a + b) = a + (n-1)b + (n-1)c + b，则a = (n-2)b + (n-2)c + c，所以当slow指针走a步时，fast走了(n-2)b + (n-2)c + c步，正好走到q点，与slow指针碰面，而这个q点正好是环的入口点。

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    //双指针法    public ListNode EntryNodeOfLoop(ListNode pHead)    {        //1、判断是否有环        ListNode slow = pHead, fast = pHead;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;                        if (slow == fast) {                break;            }        }                //不存在环        if (fast == null || fast.next == null) {            return null;        }        //存在环        //2、找到环的入口节点        slow = pHead;        while (slow != fast) {            slow = slow.next;            fast = fast.next;        }        return slow;    }}

参考：

转载地址：http://pfnii.baihongyu.com/