一个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点会重合,显然他们从环的入口点就开始重合
分享到:
相关推荐
05_JavaSE面试题:递归与迭代
弹性力学数值方法:迭代法:迭代法原理与应用.docx
区块链:科创未来(六):迭代与竞争——以太坊的Layer 2扩容之路.pdf
Java试题-4:迭代器的应用 查询修改集合可以用集合自身的方法来实现 也可以用迭代器来实现 区别在于用迭代器对集合的修改操作更加安全
在vivo数据挖掘面试题中,讨论了数组和背包问题,这些都是算法领域中的经典问题,对应着leetcode中的相关题目。 明略科技AI岗位面试题中涉及到了熵、交叉熵的概念,熵是信息论中的一个基本概念,交叉熵则是衡量两个...
弹性力学数值方法:迭代法:弹性力学迭代法的并行计算.docx
"百度面试题总结"这个资料包很可能包含了百度在招聘过程中对C++程序员的考察点,帮助应聘者更好地准备面试。 C++的基础知识点包括: 1. **基本语法**:C++的基础始于了解变量、数据类型、运算符、流程控制(如if...
迭代模式是一种设计模式,它提供了一种方法来顺序访问聚合对象的元素,而又不暴露其底层表示。在Java、C#等面向对象编程语言中,迭代器模式是常用的一种行为设计模式,它允许我们遍历集合对象的元素,而无需暴露集合...
弹性力学数值方法:迭代法:有限元法基础.docx
弹性力学数值方法:迭代法:预条件技术在弹性力学迭代法中的应用.docx
弹性力学数值方法:迭代法:弹性力学中的子结构技术.docx
弹性力学数值方法:迭代法:弹性力学中的多网格方法.docx
腾讯NOW直播竞品分析报告:迭代方向参考.pdf
弹性力学数值方法:迭代法:弹性力学数值方法中的误差控制.docx
弹性力学数值方法:迭代法:弹性力学数值模拟的收敛性分析.docx
弹性力学数值方法:迭代法:弹性力学中的有限差分法.docx
弹性力学数值方法:迭代法:共轭梯度法在弹性力学中的应用.docx
社会服务行业专题报告:AI赋能开启:迭代快速、影响广泛、全民参与.pdf
这份资源包含的110道Python面试题,以及相关的面试宝典和问题列表,将帮助求职者深入理解Python语言的关键概念,提高面试成功率。以下是一些核心的Python知识点,根据题目和资料内容,可以预期这些可能会出现在面试...
区块链:科创未来(六):迭代与竞争——以太坊的Layer 2扩容之路