题解 | #链表中环的入口结点#

题目

牛客:链表中环的入口节点 Leetcode：环形链表Ⅱ

题目分析

• 第一件事，判断是否有环，如果没有就直接返回null；
• 第二件事，找到环的入口；

思路

• 使用双指针法判断是否有环，初始时，快慢指针都指向头结点，之后慢指针每次走1步，快指针每次走2步。如果有环，则快慢指针一定会相遇。
• 如上图所示，假设环的入口节点为a，环的长度为b，假设相遇点为m。可得相遇时，慢指针走了m步，快指针走了2m步。
• 快指针先走到m点，之后在环里转了n圈又回到m点，之后两指针相遇。可得快指针走的步数2m = m + nb，即m=nb，m为环的节点的整数倍。
• 又由上图可知，任何到达环的入口节点的指针，走过的步数都为a加上环的节点数的整数倍，即a+nb=a+m; n=0,1,...。
• 相遇时，慢指针走了m步，只需要再让慢指针继续走a步，慢指针就可以到达环的入口节点。
• 为了不用计算a为多少，可以让快指针从链表的头步开始走，当快指针走到环的入口时，正好a步，两指针再次相遇，相遇点即为环的入口节点。

代码

• Java

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

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //判断是否有环
        ListNode slow = pHead;
        ListNode 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;
        
        // 找入口
        fast = pHead;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}