一亩三分地论坛

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

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

[树/链表/图] ReverseLinkedList2链表操作居然超时了

[复制链接] |试试Instant~ |关注本帖
小马3107 发表于 2015-8-13 18:22:43 | 显示全部楼层 |阅读模式

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

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

x
代码见附件。这是LintCode上做的题,leetcode应该也有。基本思路就是找到第m和第n个节点,然后将m,n之间的节点进行反转。

很奇怪为什么会超时。

因为寻找节点是O(n)复杂度,反转也是O(n)复杂度。
百思不得其解。
ReverseLinkedList2.png
stellari 发表于 2015-8-13 22:40:47 | 显示全部楼层
遇到这种情况,我建议你先推理一下:

1. 在这么短的test case上超时,肯定是出现了死循环。
2. 代码中的循环只有3处:
(a) for 循环,i和n在循环中都未被改变,所以肯定不会死循环。
(b) reverseList中的while循环,这是一个标准的4行reverse模板,应该没有问题。
(c) 主函数中的while循环,这是一个标准的链表遍历,看来也没有问题。

3. 循环代码都没有问题,那就只有一个可能,就是链表本身是有环的。
4. 原始链表肯定是没环的,所以环肯定是自己的代码引入的。
5. 自己的代码中唯一改变链表结构的就只有这么两句:
end.next = null;
beforeStart.next = reverseList(start);
那么环肯定是在这里被引入的。

这样你就把要debug的范围缩小到了一次函数调用之内,接下来我相信你应该是能够自己找到错误所在的。
回复 支持 2 反对 0

使用道具 举报

marcuscc 发表于 2015-8-13 22:44:38 | 显示全部楼层
楼主你好,我以前没用过LintCode。刚刚注册个,试着写了个可以过的。你代码的问题在于没考虑从第一个元素开始reverse。
贴上我的部分代码,请参考。
m1.PNG
result.PNG
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-13 23:17:00 | 显示全部楼层
当m=1时,你的beforeStart和start都是指向head, 这应该不是你想要的结果吧?你想要的结果是beforeStart在Start前面一个位置。所以这里应该有问题。
回复 支持 反对

使用道具 举报

 楼主| 小马3107 发表于 2015-8-14 08:17:59 | 显示全部楼层
谢谢大家。我在第38行下面加上
  1. if (m == 1) beforeStart = dummy;
复制代码
当m=1的时候把start之前的指针归位到dummy。答案就通过了。
回复 支持 反对

使用道具 举报

 楼主| 小马3107 发表于 2015-8-14 08:18:21 | 显示全部楼层
stellari 发表于 2015-8-13 22:40
遇到这种情况,我建议你先推理一下:

1. 在这么短的test case上超时,肯定是出现了死循环。

太强大了!
回复 支持 反对

使用道具 举报

 楼主| 小马3107 发表于 2015-8-14 08:20:47 | 显示全部楼层
marcuscc 发表于 2015-8-13 22:44
楼主你好,我以前没用过LintCode。刚刚注册个,试着写了个可以过的。你代码的问题在于没考虑从第一个元素开 ...

谢谢!通过了 好强大!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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