来源 | 博文视点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算法来统计用户特征等。