java 如何检测链表中的环路?

在java中,由于各种原因(如果没做好线程安全,则在多线程中较常见),链表容易形成环路。我最早在HashMap的研究中接触过这个问题(在Jdk 1.8以前的版本中,扩容方法有几率让bucket中的链表形成环路),当时并没有在意,直到最近看到了一篇非常好的文章,才打算研究一下这个问题。

参考:http://blog.jobbole.com/106227/

 

一、实现环状链表

我们首先实现一个环状链表。

LinkedList<T>.java

我们可以看到同一Node对象node被insert了两次,形成了环状链表。很明显,这段代码会在traversal方法遍历链表时陷入死循环,导致java.lang.StackOverflowError。

运行结果为:

内存如愿以偿地爆掉了…那么问题来了,如何检测链表是否有环?能不能在内存爆掉之前就把问题解决?

二、发现环路

(1)穷尽法

我们首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。

代码的具体实现为:

Traversal1.java

运行结果为:

假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2,可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

显然,穷举法需要比较的次数太多,时间复杂度不太理想。

(2)优化穷举法

穷举法比较次数太多,效率不高。我们能否找到一种方法,在比较次数最少的情况下找到重复数据?我们应该能很快反应,Hash算法应该是最优解。

我们首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。

代码的具体实现为:

Traversal2.java

假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

其实这个方法和方案一类似,只是使用了HashSet作为数据的载体而已,原理还是需要各种比较,但是理论上性能更好。

(3)追逐法

在生活中有这样的例子:两个运动员A、B进行一场赛跑,他们在同一地点起跑。A运动员速度快,B运动员速度慢。如果跑道不是环形的,运动员B永远不可能追上运动员A。如果跑道是环形的,在两人跑了一段时间后,速度快的运动员A必然会追上并超过速度慢的运动员B。

因此,只要“运动员A”追上了“运动员B”,就能证明跑道是环形的。

我们首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

代码的具体实现为:

Chase.java

假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S*K次,K为正整数(为什么是S*K次,有心的同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)。

三、拓展

(1)找到两个单链表的交点

双指针同时从头遍历两个链表,指针到结尾之后跳到另一个链表的头继续遍历。两指针相交之处即为交点。

Cross.java

运行结果为:

(2)找到环状链表的环路开始节点

参考:http://blog.csdn.net/u011373710/article/details/54024366

个人感觉这个算法比较难以理解。我参照上面的链接画了很久的图,才大概明白这种算法的巧妙之处。

FindLoopStart.java

运行结果为:

三、总结

个人感觉“追逐”算法非常巧妙,后面的拓展有一定难度,一开始真的很难想到(我只能想到)。需要一定的算法基础。看来平时还是需要多多锻炼。