链表 - 判断链表是否有环以及环的入口

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

一. 什么是链表的环?

单链表出现循环的情况就是链表的环。
所以,寻找环的入口就是找到循环开始的地方。

二. 解决方案

  • 快慢指针
    • 理解该方法需要我们推导一条原理
      链表 - 判断链表是否有环以及环的入口_第1张图片
    • 如图所示,x为链表入口到环入口的距离,y为环入口到快慢指针相遇点的距离,z为相遇点到环入口的距离。
    • 同时,环的总长度为L,即L = y + z
    • 设置快指针,每次走2个节点,记为2S。
    • 设置慢指针,每次走1个节点,记为1S。


    • 化简得到:x = (n - 1)L + z
    • 其中n是快指针比慢指针多走的循环数,当n = 1时,x = z,也就是说,当快指针只比慢指针多走一圈就相遇的话,链表入口到环入口的距离=相遇点到环入口的距离。当n != 1 时,道理一样,只不过快指针跑多几圈而已。
    • 正是基于上面的结论,可以在快慢指针第一次相遇的地方重置快指针的位置,使快指针回到链表入口,慢指针不动。然后,两个指针以相同的速度在运动,再次相遇的地方就是环入口。
function EntryNodeOfLoop(pHead)
{
    let fast = pHead;
    let slow = pHead;
    while(fast && fast.next){
        fast = fast.next.next;// 快指针一次走两步
        slow = slow.next;// 慢指针一次走一步
        if(fast == slow){ // 第一次相遇重置快指针的位置以及速度
            fast = pHead;
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;// 再次相遇的地方就是环入口
        }
    }
    return null;
}

你可能感兴趣的