`
Iam42
  • 浏览: 275494 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

百度面试题:迭代打开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点会重合,显然他们从环的入口点就开始重合

1
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics