送书 | 当代程序员是如何被算法面试逼哭的
脚本之家
你与百万开发者在一起
来源 | 博文视点Broadview | 文末赠书
题 目
有一个单向链表，链表中有可能出现“环”，就像下图这样。那么，如何用程序来判断该链表是否为有环链表呢？
— — 方法 1 — —
首先从头节点开始，依次遍历单链表中的每一个节点。每遍历一个新节点，就从头检查新节点之前的所有节点，用新节点和此节点之前所有节点依次做比较。如果发现新节点和之前的某个节点相同，则说明该节点被遍历过两次，链表有环；如果之前的所有节点中不存在与新节点相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
就像图中这样，当遍历链表节点7时，从头访问节点5和节点3，发现已遍历的节点中并不存在节点7，则继续往下遍历。
当第2次遍历到节点2时，从头访问曾经遍历过的节点，发现已经遍历过节点2，说明链表有环。
假设链表的节点数量为n，则该解法的时间复杂度为O(n2)。由于并没有创建额外的存储空间，所以空间复杂度为O(1)。
— — 方法 2 — —
姑且算是种方法，效率有没有可能更高？
首先创建一个以节点ID为Key的HashSet集合，用来存储曾经遍历过的节点。然后同样从头节点开始，依次遍历单链表中的每一个节点。每遍历一个新节点，都用新节点和HashSet集合中存储的节点进行比较，如果发现HashSet中存在与之相同的节点ID，则说明链表有环，如果HashSet中不存在与新节点相同的节点ID，就把这个新节点ID存入HashSet中，之后进入下一节点，继续重复刚才的操作。
遍历过5、3的效果图
遍历过5、3、7、2、6、8、1的效果图
当再一次遍历节点2时，查找HashSet，发现节点已存在。
由此可知，链表有环。
这个方法在流程上和方法1类似，本质的区别是使用了HashSet作为额外的缓存。
假设链表的节点数量为n，则该解法的时间复杂度是O(n)。由于使用了额外的存储空间，所以算法的空间复杂度同样是O(n)。OK，这种方法在时间上已经是最优了。
有没有可能在空间上也得到优化？
没关系，今天就到这里，回家等通知吧。
— — 方法 3 — —
小灰，刚刚的面试结果怎么样？
有环链表判断是基础，面试官都喜欢考查
有一个巧妙的方法——利用两个指针
首先创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。
第1步，p1和p2都指向节点5。
第2步，p1指向节点3，p2指向节点7。
第3步，p1指向节点7，p2指向节点6。
第4步，p1指向节点2，p2指向节点1。
第5步，p1指向节点6，p2也指向节点6，p1和p2所指相同，说明链表有环。
学过小学奥数的读者，一定听说过数学上的追及问题。此方法就类似于一个追及问题。
在一个环形跑道上，两个运动员从同一地点起跑，一个运动员速度快，另一个运动员速度慢。当两人跑了一段时间后，速度快的运动员必然会再次追上并超过速度慢的运动员，原因很简单，因为跑道是环形的。
假设链表的节点数量为n，则该算法的时间复杂度为O(n)。除两个指针外，没有使用任何额外的存储空间，所以空间复杂度是O(1)。
学习算法，我们不需要死记硬背那些冗长复杂的背景知识、底层原理、指令语法……需要做的是领悟算法思想、理解算法对内存空间和性能的影响，以及开动脑筋去寻求解决问题的最佳方案。《漫画算法：小灰的算法之旅》的出现给算法这颗“炮弹”包上了“糖衣”，在轻松间领略算法的魅力，入门算法与数据结构。
本书通过虚拟的主人公小灰的心路历程，用漫画的形式讲述了算法和数据结构的基础知识、复杂多变的算法面试题目及算法的实际应用场景。
本 书 结 构
第1章 算法概述
介绍了算法和数据结构的相关概念，告诉大家算法是什么，数据结构又是什么，它们有哪些用途，如何分析时间复杂度，如何分析空间复杂度。
第2章 数据结构基础
介绍了最基本的数据结构，包括数组、链表、栈、队列、哈希表的概念和读写操作。
第3章 树
介绍了树和二叉树的概念、二叉树的各种遍历方式、二叉树的特殊形式——二叉堆和优先队列的应用。
第4章 排序算法
介绍了几种典型的排序算法，包括冒泡排序、快速排序、堆排序、计数排序、桶排序。
第5章 面试中的算法
介绍了10余道职场上流行的算法面试题及详细的解题思路。例如怎样判断链表有环，怎样计算大整数相加等。
第6章 算法的实际应用
介绍了算法在职场上的一些应用，例如使用LRU算法来淘汰冷数据，使用Bitmap算法来统计用户特征等。
在本文下方留言，发表您在算法面试过程中的经验感想，机会总是靠自己去争取来的！小编将对留言进行精选，被精选的留言才会在留言区显示并获得相应的楼层（由于微信留言功能限制，最多只能显示100条）。
踩楼送书活动获奖须知：
1、活动结束时踩中已放在百度云文件中指定楼层的精选留言将获得 《漫画算法：小灰的算法之旅》一本，共6名中奖者
2、活动结束后我们会在本公众号公布中奖楼层的解压密码，并在3个工作日内联系到获奖用户将奖品送出（收到奖品的小伙伴欢迎来留言区晒晒。）
3、获奖楼层下载地址（文件解压密码会在2019年7月30日推送的中奖文章中公布）
百度云链接: https://pan.baidu.com/s/1eyuRFrxTquTLs9Q9JuDBHA
提取码: ftnu
活动时间
活动时间：即日起至2019年7月30日下午4点整
精选书单 点蓝字即可
更多好书请关注脚本之家官方书店