【Java算法题解】剑指 Offer II 022. 链表中环的入口节点

简介: 解析先通过快慢指针判断有无环无环直接返回null有环假设起点到环起点的距离是a,环的长度是k,且此时A、B在距离环起点x距离处相遇。

解析

先通过快慢指针判断有无环

无环

直接返回null

有环

假设起点到环起点的距离是a,环的长度是k,且此时A、B在距离环起点x距离处相遇。

即慢指针再走x步就到达环的入口,此时slow走过的距离

a + nk + (k - x)

快指针走过的距离:

a + mk + (k - x)

由快慢的定义可知:

a + mk + (k - x) = 2 * (a + nk + (k - x))

化简得:

a = (m - 2n -1)k + x

可知a为k的整数倍加x,而AB相遇的位置再走x步恰是环入口,所以此时让其中一个指针指向起点,然后同步走,一定能在环入口相遇!

所以可得代码:

package com.javaedge;
/**
 * @author JavaEdge
 * @date 2021/8/17
 */
public class DetectCycle {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean isCircled = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                isCircled = true;
                break;
            }
        }
        if (!isCircled) {
            // 无环
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
目录
打赏
0
0
0
0
1891
分享
相关文章
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
基于粒子群算法的网络最优节点部署优化matlab仿真
本项目基于粒子群优化(PSO)算法,实现WSN网络节点的最优部署,以最大化节点覆盖范围。使用MATLAB2022A进行开发与测试,展示了优化后的节点分布及其覆盖范围。核心代码通过定义目标函数和约束条件,利用PSO算法迭代搜索最佳节点位置,并绘制优化结果图。PSO算法灵感源于鸟群觅食行为,适用于连续和离散空间的优化问题,在通信网络、物联网等领域有广泛应用。该算法通过模拟粒子群体智慧,高效逼近最优解,提升网络性能。
|
22天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
85 25
基于GA遗传优化的WSN网络最优节点部署算法matlab仿真
本项目基于遗传算法(GA)优化无线传感器网络(WSN)的节点部署,旨在通过最少的节点数量实现最大覆盖。使用MATLAB2022A进行仿真,展示了不同初始节点数量(15、25、40)下的优化结果。核心程序实现了最佳解获取、节点部署绘制及适应度变化曲线展示。遗传算法通过初始化、选择、交叉和变异步骤,逐步优化节点位置配置,最终达到最优覆盖率。
ODPS MR节点跑graph连通分量计算代码报错java heap space如何解决
任务启动命令:jar -resources odps-graph-connect-family-2.0-SNAPSHOT.jar -classpath ./odps-graph-connect-family-2.0-SNAPSHOT.jar ConnectFamily 若是设置参数该如何设置
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
经典算法之链表篇(三)
经典算法之链表篇(三)
109 4
|
4月前
|
经典算法之链表篇(二)
经典算法之链表篇(二)
|
4月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
67 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等