一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 321|回复: 5
收起左侧

[算法题] 求解法

[复制链接] |试试Instant~ |关注本帖
mlfma 发表于 2015-10-1 03:12:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
如果两个linked list intersect的话如何找到merge point。 有环的情况


我只想到用hashmap来解
plich 发表于 2015-10-1 06:15:22 | 显示全部楼层
1.找出一个汇合点
2. 测量两个list 到 汇合点的距离
3.调整起点以致距离相等
4.走过去,撞到了就返回那个值

O(n)时间 O(1)空间
回复 支持 反对

使用道具 举报

 楼主| mlfma 发表于 2015-10-1 06:51:19 | 显示全部楼层
请问如何找汇合点?
回复 支持 反对

使用道具 举报

plich 发表于 2015-10-1 10:37:02 | 显示全部楼层
mlfma 发表于 2015-10-1 06:51
请问如何找汇合点?

两个指针,一个一次跳两步,一个一次跳一步,早晚会撞上。
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-10-7 01:11:13 | 显示全部楼层
看到这个问题觉得还挺有意思。首先假设两个链表都没有环但是相交, 怎么找intersect呢?简单的办法就是遍历2个链表然后算出各自的长度,然后考虑那个offset再遍历一次输出第一个相交点。然后这个问题就是怎么把有环的情况reduce到没环的情况,当然这必须假设汇合点不在环内,否则有2个汇合点。这个时候要找到环的起点,然后把这个起点当成相交后链表的终点。
回复 支持 反对

使用道具 举报

lrn0304 发表于 2015-10-29 05:44:51 | 显示全部楼层
这样想, 现在有个环, 那楼主画个图, 如果两个链表相交, 是不是交点肯定在环上吧, 那交点怎么找呢? 单链表只有一个指出的指针吧? 那交点后的都是环是吧, 所以有思路了吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 12:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表