考试结束，班级平均分只拿到了年级第二，班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰，有人知道世界第二高峰是什么吗？正当班主任要继续发话，只听到角落默默响起来一个声音:”乔戈里峰”

题目

每天一道剑指offer-链表中环的入口结点 https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目详述

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

题目详解

思路

• 使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇说明有环；
• 有环以后，需要寻找环入口节点，已经找到了一个环的中的节点，利用这个节点，去往下遍历，由于是环，所以这个节点肯定会和自身相遇，相遇以后，记录相遇过程中走的步数，就是环的长度
• 知道环的长度以后，然后再利用快慢指针的思想，快指针先走环长度，然后快慢指针再一起走，这样因为快指针先走了环的长度，当两者相遇肯定是环的入口节点相遇（为啥呢，因为快慢指针肯定会进入环里面，而由于快指针先走了环的长度，所以也就是一个周期，所以只要进入环，那么这两个指针必然相遇）

代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    boolean flag = true;
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return null;
        ListNode pNode = judgeHasChain(pHead);//判断是否有环
        if(pNode != null)
        {
            int lengthChain = 1;
            ListNode pNodeCopy = pNode.next;
            while(pNodeCopy != pNode)
            {//这个节点已经在环里面了！
                lengthChain++;
                pNodeCopy = pNodeCopy.next;//计算环的长度
            }
            ListNode fast = pHead;
            ListNode slow = pHead;
            int temp = 0;
            while(temp < lengthChain)
            {//快指针先走环的长度
                fast = fast.next;
                temp++;
            }
            while(fast != slow)
            {//快慢指针一起走，因为快指针先走了环长度，当慢指针刚一进环，由于快指针刚好多走了环长度，所以快指针整好走了一个环的周期呀，所以快指针必然也在环的入口
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }
    private ListNode judgeHasChain(ListNode pHead)
    {
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != slow)
        {
            if(fast != null && fast.next != null)
            {//快指针走一步
                fast = fast.next;
            }else{
                flag = false;
                break;
            }
            if(slow != null && slow.next != null)
            {//慢指针走一步
                slow = slow.next;
            }else{
                flag = false;
                break;
            }
            if(fast == slow)
            {//两者相等，说明相遇了，有环
                return fast;
            }else{
                fast = fast.next;//快指针多走一步
            }
        }
        if(flag)
            return fast;
        return null;
    }
}