个人中心
首页 > 面试有戏 > 面试杂谈 > 正文

程序面试题:链表系列之有环的链表!

来源:五百丁 作者:chinaz_zy

程序原题


Given a linked list, determine if it has a cycle in it. 


题目翻译


给定一个链表,判断其中是否含有环。


题目分析


这是一道经典的不能再经典的面试题……


请看过这道题目的同学们先不要脱口而出答案。我们来假设我们是第一次看到这个题,应该从哪儿着手呢?


一个最最自然的想法是——记住哪些节点出现过,哪些没有。重复出现了节点就说明了链表中有环。我们可以:1)在每个走过的节点留下一些“印记”,这样会弄脏输入数据;2)我们用一个Set来记录每一个走过节点的内存地址,这其实在我看来是一个很自然很好的解法,唯一的缺点是需要用O(n)的额外空间。


这道题的“标准解答”是——“快慢指针技巧”。slow指针和fast指针开始同时指向头结点head,fast每次走两步,slow每次走一步。如果链表不存在环,那么fast或者fast.next会先到None。如果链表中存在环路,则由于fast指针移动的速度是slow指针移动速度的两倍,所以在进入环路以后,两个指针迟早会相遇,如果在某一时刻slow==fast,说明链表存在环路。


遗憾的是,如果我是面试官,在候选人说出这个答案的时候我会判定这个候选人肯定看过这个标准解答……从而我会把面试重点换成编程风格和写程序是否熟练……并且会在心里默默准备下一道题目……


但是如果候选人能够分析出如上几种可能的解答再给出最优解答,那一定是会大大加分的!


程序实现


程序实现.jpg

0

二维码

1.五百丁遵循行业规范,任何转载的稿件都会明确标注作者和来源;

2.五百丁的原创文章,请转载时务必注明文章作者和"来源:五百丁",不尊重原创的行为五百丁或将追究责任;

3.作者投稿可能会经五百丁编辑修改或补充。

Word简历模板

  • 最美简历合集
  • WORD简历模板
  • 线轴简历模板 清爽风格
  • 图形化创意简历模板合集
客服在线时间:9:00-18:00

Copyright © 2014-2016 500d.me. All Rights Reserved.

个人中心 - 帮助中心 - 网站地图 - 粤ICP备14072413号