博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
链表中环的入口结点
阅读量:6878 次
发布时间:2019-06-26

本文共 942 字,大约阅读时间需要 3 分钟。

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

  1. 第一步,找环中相汇点。分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。
  2. 第二步,找环的入口。接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead) {        if (pHead == null)            return null;        ListNode p1 = pHead, p2 = pHead;        while (p2 != null && p2.next != null) {            p1 = p1.next;            p2 = p2.next.next;            if (p1 == p2) {                p2 = pHead;                while (p1 != p2) {                    p1 = p1.next;                    p2 = p2.next;                }                if (p1 == p2)                    return p1;            }        }        return null;    }}

 

转载于:https://www.cnblogs.com/wxisme/p/5834383.html

你可能感兴趣的文章
if case 语句 find locate 文件查找 和 压缩解压缩工具 简介
查看>>
Linux常用命令——tr
查看>>
检测 ip 是否断开,并使用邮箱报警
查看>>
整理第一周学习C的知识点
查看>>
Spring Data JPA 实例查询
查看>>
ping多线程
查看>>
PMP每日一题
查看>>
python中struct.unpack的用法
查看>>
解决物理内存足够时VMware 提示物理内存不足。。。
查看>>
java socket常见异常
查看>>
Dubbo与Zookeeper、SpringMVC整合和使用
查看>>
Spring中的属性scope
查看>>
SpringApplication你不知道的那些事!
查看>>
为什么比别人办事效率慢?因为你没用这几款强大的搜索软件!
查看>>
linux菜鸟基础学习 (二) 中篇
查看>>
配置网络
查看>>
0021-使用JDBC向Kudu表插入中文字符-cast的秘密
查看>>
Kubernetes 1.14发布:对Windows节点的生产级支持、Kubectl更新与持久本地卷
查看>>
PHP获取未来七天的日期和星期
查看>>
web防火墙的开通和部署
查看>>