64,637
社区成员
发帖
与我相关
我的任务
分享今天的一道面试题,我到现在还想不出怎么做...
面试官:给你一条单链表,如何判断它是否是环形链表
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
...全文
请发表友善的回复…
发表回复
ameigame 2009-12-05
- 打赏
- 举报
仔细想了下,是我模糊了概念了,感谢各位解答,结贴
ameigame 2009-12-05
- 打赏
- 举报
[Quote=引用 15 楼 mstlq 的回复:]
遇到这样的链表，楼主的方法直接就死循环了……
C/C++ code*-->*-->*-->*-->*-->*-->*-->*^|||*<--*<--*
[/Quote]
这个我知道,之前就有考虑过,但既然说明是单链表了,你示例的这个结构也属于单链表的范畴吗,是不是我对概念还不够清楚
遇到这样的链表，楼主的方法直接就死循环了……
C/C++ code*-->*-->*-->*-->*-->*-->*-->*^|||*<--*<--*
[/Quote]
这个我知道,之前就有考虑过,但既然说明是单链表了,你示例的这个结构也属于单链表的范畴吗,是不是我对概念还不够清楚
shuiqin 2009-12-03
- 打赏
- 举报
强，学习了。。。
do_fork 2009-12-03
- 打赏
- 举报
[Quote=引用 14 楼 ameigame 的回复:]
引用 2 楼 do_fork 的回复:
快慢指针，一个每次前进2节点，一个每次前进1节点，如果快的那个追上慢的那个，那就是存在循环了
这样子效率高吗?
[/Quote]
已经是O(n)的算法了，不可能小于这个时间复杂度
引用 2 楼 do_fork 的回复:
快慢指针，一个每次前进2节点，一个每次前进1节点，如果快的那个追上慢的那个，那就是存在循环了
这样子效率高吗?
[/Quote]
已经是O(n)的算法了，不可能小于这个时间复杂度
zhaixingchen 2009-12-03
- 打赏
- 举报
学习了
taodm 2009-12-03
- 打赏
- 举报
呃，楼主啊，买本《C专家编程》吧，这钱省不得。
下回你就可以直接回面试官：后面的3问咱也知道答案，直接帮你说了吧。
下回你就可以直接回面试官：后面的3问咱也知道答案，直接帮你说了吧。
immjt 2009-12-03
- 打赏
- 举报
快慢指针的效率确实不高，只是它解决的更全面
kostion 2009-12-03
- 打赏
- 举报
学习了
luokun3221 2009-12-03
- 打赏
- 举报
学习了
mstlq 2009-12-03
- 打赏
- 举报
遇到这样的链表，楼主的方法直接就死循环了……
*-->*-->*-->*-->*-->*-->*-->*
^ |
| |
*<--*<--*ameigame 2009-12-03
- 打赏
- 举报
[Quote=引用 2 楼 do_fork 的回复:]
快慢指针，一个每次前进2节点，一个每次前进1节点，如果快的那个追上慢的那个，那就是存在循环了
[/Quote]
这样子效率高吗?
快慢指针，一个每次前进2节点，一个每次前进1节点，如果快的那个追上慢的那个，那就是存在循环了
[/Quote]
这样子效率高吗?
ameigame 2009-12-03
- 打赏
- 举报
单链表的话,快慢指针的效率不是更慢吗?
blackbillow 2009-12-03
- 打赏
- 举报
[Quote=引用楼主 ameigame 的回复:]
面试官:给你一条单链表,如何判断它是否是环形链表
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
[/Quote]
如果头结点不在这个环中，你就死循环了
面试官:给你一条单链表,如何判断它是否是环形链表
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
[/Quote]
如果头结点不在这个环中，你就死循环了
xjj210130 2009-12-03
- 打赏
- 举报
面试前多看一些面试的经典题目，呵呵，
kingstarer 2009-12-03
- 打赏
- 举报
[Quote=引用楼主 ameigame 的回复:]
面试官:给你一条单链表,如何判断它是否是环形链表
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
[/Quote]
面试你的人在网上看到这道题就来考你了
其实你这个做法效率比快慢指针更高
但是有一个问题，如果链表是那种六型或者九型的那就死循环了，快慢指针没这个问题
面试官:给你一条单链表,如何判断它是否是环形链表
我:如果是单链表,就把头结点记录下来,进循环,如果回到头结点或者遇到Null就break,这样不就可以了吗
面试官:为什么你不想用两个指针来追呢?
我:单链表就用一个指针就够了
面试官:嗯,如果这个链表有十万个节点,这样效率就太慢了,有没有更好的算法
我:囧~~~~
难道是sizeof(结构体)*N地跳内存访问???
请高手指教
[/Quote]
面试你的人在网上看到这道题就来考你了
其实你这个做法效率比快慢指针更高
但是有一个问题，如果链表是那种六型或者九型的那就死循环了，快慢指针没这个问题
dqdx_zch 2009-12-03
- 打赏
- 举报
那要是用三个火更多，岂不是更快？
当然要对小的链表进行一下检测。
当然要对小的链表进行一下检测。
dqdx_zch 2009-12-03
- 打赏
- 举报
哦，快慢指针，学习了！
loveour 2009-12-03
- 打赏
- 举报
p2 = p2->next->next;
loveour 2009-12-03
- 打赏
- 举报
[Quote=引用 3 楼 do_fork 的回复:]
面色同学是熬夜呢，还是跟我一样已经早起了?
[/Quote]
早起...我佩服你...
这道题目还是见挺多的，设置两个指针，一个每循环走一步，一个走两步，例如p1,p2,像这样
p1 = p1->next;
p2 = p2->next;
这样循环次数会减少很多...不是按大小跳内存访问，而是访问下一个节点的下一个节点
面色同学是熬夜呢，还是跟我一样已经早起了?
[/Quote]
早起...我佩服你...
这道题目还是见挺多的，设置两个指针，一个每循环走一步，一个走两步，例如p1,p2,像这样
p1 = p1->next;
p2 = p2->next;
这样循环次数会减少很多...不是按大小跳内存访问，而是访问下一个节点的下一个节点
winner1400 2009-12-03
- 打赏
- 举报
第一次听过快慢指针，囧死了~
加载更多回复（8）
