链表中环的入口结点

本贴最后更新于 2450 天前,其中的信息可能已经东海扬尘

题目描述

一个链表中包含环,请找出该链表的环的入口结点。

解题思路

行走轨迹

两个结点同时运行,其中快结点 fast 一次走两个结点,慢结点 slow 一次走一个结点。

假设 x 为环前面的路程(黑色路程),a 为环入口到相遇点的路程(蓝色路程,假设顺时针走), c 为环的长度(蓝色 + 橙色路程)

两结点相遇时,快结点走过的路程:

L_f=x+n*c+a

慢节点走过的路程:

L_s=x+m*c+a

且速度 fast 是 slow 的二倍,所以:

L_f=2L_s

于是,可以推出:

x=(n-2*m)*c-a=(n-2*m-1)*c+c-a

也就是说,环前面的路程=环长度的整数倍 +c-a。
而 c-a 就是橙色部分,也就是从起点走到入口点的路程相当于走几个环 + 橙色部分的路径。
那么我们让 slow 在相遇点走,fast 在起始点走(一次只走一个结点),最后一定是在环的入口相遇。

时间复杂度:O(n)

空间复杂度:O(1)

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null || pHead.next.next == null)
            return null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        
        while (fast != slow) {
            if (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else
                return null;
        }
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...