百度面试题：迭代打开url问题

一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。这样构成一个单链表。给两条这样单链表，判断里面是否存在同样的url。url以亿级计，资源不足以hash。

本题可以抽象为有环和无环情况下的链表交叉问题：

 

情况一：两条单链表均无环

     最简单的一种情况，由于两条链表如果交叉，他们的尾节点必然相等（Y字归并），所以只需要判断他们的尾节点是否相等即可。

 

情况二：两条单链表均有环

    这种情况只需要拆开一条环路（注意需要保存被设置成null的节点），然后判断另一个单链表是否仍然存在环路，如果存在，说明无交叉，反之，则有交叉的情况。

 

情况三:两条单链表，一条有环路，一条无环路

    这种情况显然他们是不可能有交叉的

 

附：如何判断一条单链表是否存在环路，以及找出环路的入口

快慢指针：在表头设置两个指针fast与slow，fast指针与slow指针同时向前移动，但是fast每次移动2个节点，slow每次移动1个节点，若fast指向null或者fast==slow时停止，这时如果fast指向null，则说明没有环路，若fast==slow则说明有环路。

找环路入口：当fast==slow时，将fast重新指向表头。slow原地不动。然后fast和slow在同时以每次一个节点的速度向前移动，当他们再次重合时，就是环路入口。证明如下：

1.证明fast和slow肯定会重合

在slow和fast第一次相遇的时候，假定slow走了n步骤，环路的入口是在p步的时候经过的，那么有slow走的路径： p+c ＝ n； c为p1和p2相交点，距离环路入口的距离；fast走的路径： p+c+k*L = 2*n；   L为环路的周长，k是整数。显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点同时p2从头开始走的话，经过n步，也会达到p+c这点。

2.fast和slow在p+c点会重合，显然他们从环的入口点就开始重合