博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
判断链表是否有环,找链表中间节点,判断两个链表是否相交
阅读量:7142 次
发布时间:2019-06-29

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

判断是否有环和查找中间节点

使用两个指针,p1每次前进1个节点,p2每次前进2个节点,如果链表有环,则最后两个指针指向的节点将会重合,若无环,则p2最后将走到链表尾,当p2走到链表尾时,p1指向的节点就是中间节点

检测环的入口

当p1p2重合以后,让p2回到表头,步长设为1重新开始走,当p1p2再次重合时,重合点即为环入口

证明:

如图表头到环入口长度为l1,环的长度为l2,环的入口为h点,p2p1第一次重合点为h'点,设hh'长度为l3,则有

在第一次重合时

p1走过的路程 = l1 + l3

p2走过的路程 = l1 + l3 + n * l2 = 2 * (l1+l3) 

=> l2 = (l1 + l3) / n   # n为p2在环上走过的圈数

p2速度置为1重新走起,当走过l1的路程时到达环入口

p1此时也走过l1的路程, 则从环口开始,p1共走过的路程为 l1 + l3 + l1 - l1 = l1 + l3(减去了表头到环口路程) = n * l2 正好走了n圈到达环口

故p1,p2第二次重合时就是在环口

 

检测链表是否相交

将其中一个链表首尾相连,检测另一个链表是否存在环,如果存在则相交,环的入口即为两个链表的交点

 

转载地址:http://xdgrl.baihongyu.com/

你可能感兴趣的文章
xen虚拟化里常用的一些配置
查看>>
在用vi编辑文件时遇到“Terminal too wide”的提示
查看>>
RHEL6和RHEL7的变化
查看>>
VMware 虚拟机设置U盘启动(老毛桃 PE)
查看>>
程序员注意了!这样的公司千万不要去!
查看>>
文件服务器--samba和ftp的搭建
查看>>
我的友情链接
查看>>
ubuntu 14.10桌面登陆失败
查看>>
java并发编程,ThreadLocal源码解析
查看>>
textbox只能输入数字
查看>>
Summer School实验二
查看>>
sed命令的使用及案例
查看>>
GoLang环境配置
查看>>
JAVA构建缓存
查看>>
JS中使用正则表达式
查看>>
我的友情链接
查看>>
VM with share disk configuration
查看>>
解决:Loading kernel module CAP_SYS_MODULE CAP_NET_ADMIN alias netdev-eth0 instead
查看>>
oracle 常用查询
查看>>
QT常用类
查看>>