`

【100题】第七题(单链表相交)

 
阅读更多
题目:给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交,为了简化问题,我们假设俩个链表均不带环。

问题扩展:
1,如果链表可能有环列?
2,如果需要求出俩个链表相交的第一个节点列?

解答:

一,关于链表有环的思考

理解: 1,如何判断链表有环?

思考:单链表有环的判断?什么意思?一直向后递归递归到p->next=NULL;不就完了?

更正:如果一直向后递归,假如存在环的话,会出现死循环。

方法:【一】:可以做标记的话,在第一个节点做上标记。若访问到标记节点则有环,若访问到NULL则无环。(这种方法不可取,只在所有节点构成一个整环时才可以

下图:

【二】:不可以做标记的话,设置两个节点slow,fast。slow每次走一步,fast每次走两步。如果slow指针跟fast指针重合则表示有环。

【三】:应该还有方法待思考……

2,如何判断环的长度

记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。

3,如何找到环的入口在哪里?

有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。(证明在后面附注)

4,带环链表的长度是多少?

问题2求出环的长度,问题3求出头指针到连接点的距离。两者相加等于链表长度。

程序源码:(待续)

寻找环的入口的源码:

寻找环入口方法二:亦可以用类似与hash表的方法,即设立一个数组,将链表结点中的值做数组下标,当赋值冲突时就是环的接入点

创建一个有环的链表

二,分析与解法

A----B----C------D、

I-----J----NULL

/

E-----F-----G------H

这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相交的情况,而且释放了其中一个链表的所有节点,那样就会造成信息的丢失,并且另一个与之相交的链表也会受到影响,这是我们不希望看到的。在特殊的情况下,的确需要出现相交的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
【解法一】直观的想法
看到这个问题,我们的第一个想法估计都是,“不管三七二十一”,先判断第一个链表的每个节点是否在第二个链表中。这种方法的时间复杂度为 O(Length(h1) * Length(h2))。可见,这种方法很耗时间。


【解法二】利用计数的方法(hash表 最简单)
很容易想到,如果两个链表相交,那么这两个链表就会有共同的节点。而节点地址又是节点的唯一标识。所以,如果我们能够判断两个链表中是否存在地址一致的节点,就可以知道这两个链表是否相交。一个简单的做法是对第一个链表的节点地址进行 hash 排序,建立hash 表,然后针对第二个链表的每个节点的地址查询 hash 表,如果它在 hash 表中出现,那么说明第二个链表和第一个链表有共同的节点。这个方法的时间复杂度为 O(max(Length(h1)
+ Length(h2)))。但是它同时需要附加 O(Length(h1))的存储空间,以存储哈希表。虽然这样做减少了时间复杂度,但是是以增加存储空间为代价的。是否还有更好的方法呢,既能够以线性时间复杂度解决问题,又能减少存储空间?


【解法三】链接“头尾”判断环法
由于两个链表都没有环,我们可以把第二个链表接在第一个链表后面,如果得到的链表有环,则说明这两个链表相交。否则,这两个链表不相交这样我们就把问题转化为判断一个链表是否有环。链表有环的情况判断一个链表是否有环,也不是一个简单的问题,但是需要注意的是,在这里如果有环,则第二个链表的表头一定在环上,我们只需要从第二个链表开始遍历,看是否会回到起始点就可以判断出来。最后,当然可别忘了恢复原来的状态,去掉从第一个链表到第二个链表表头的指向。这个方法总的时间复杂度也是线性的,但只需要常数的空间。
【解法四】最后结点地址比较法
仔细观察题目中的图示,如果两个没有环的链表相交于某一节点的话,那么在这个节点之后的所有节点都是两个链表所共有的。那么我们能否利用这个特点简化我们的解法呢?困难在于我们并不知道哪个节点必定是两个链表共有的节点(如果它们相交的话)。进一步考虑“如果两个没有环的链表相交于某一节点的话,那么在这个节点之后的所有节点都是两个链表共有的”这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口。

先遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则,不相交。这样我们就得到了一个时间复杂度,它为 O((Length(h1) + Length(h2)),而且只用了一个额外的指针来存储最后一个节点。这个方法比解法三更胜一筹。



【如果两个有环】判断第一个链,直链跟环交点为O1,判断第二个链,直链跟环交点为O2。

比较O1跟O2地址,如果相等则相交,否则从O1遍历,每次与O2地址比较,直到回到O1。期间有相等的则相交,否则不想交。

分享到:
评论

相关推荐

    算法大全-面试题-数据结构.docx

    包括单链表反转、找出单链表的倒数第4个元素、找出单链表的中间元素、删除无头单链表的一个节点、两个不交叉的有序链表的合并、有个二级单链表的转换、一级单链表的交换、判断单链表是否有环、判断两个单链表是否...

    大数据结构+算法面试100题.pdf

    【大数据结构+算法面试100题.pdf】的文件涵盖了多方面的计算机科学和技术知识点,主要集中在数据结构和算法的应用上。以下是对其中几个问题的详细解释: 1. **二元查找树转双向链表** - 二元查找树(BST)是一种...

    算法大全-面试题-数据结构

    10. **两个单链表相交,计算相交点**:与上一个问题类似,同步移动两个指针,但无需预先判断是否相交,相遇点即为相交点。 11. **用链表模拟大整数加法运算**:将大整数转化为链表,逐位相加并处理进位,最后将结果...

    算法,面试题

    两个单链表相交,计算相交点 - **原理**: 参考判断两个单链表是否相交的方法,找到第一个相交节点。 - **步骤**: 1. 遍历两个链表,确定哪个链表更长。 2. 调整起点,使两个链表的剩余长度相同。 3. 同时遍历两...

    算法大全-面试题-数据结构1

    12. **两个单链表相交的交点**:两个链表的交点位置可以通过计算它们各自到交点的距离,然后将距离短的链表的头节点向前移动两者距离差,然后两个指针同时移动,相遇点即为交点。 13. **用链表模拟大整数加法**:...

    算法大全-面试题-链表-栈-二叉树-数据结构.docx

    10. **两个单链表相交,计算相交点** - 先分别找出两个链表的长度,然后从较长链表的头开始,向短链表的长度方向前进,到达相交点。 11. **用链表模拟大整数加法运算** - 将大整数的每一位表示为链表的节点,然后...

    算法大全-面试题-链表-栈-二叉树-数据结构

    10. **两个单链表相交,计算相交点** 相交点即为上一点所述的相遇节点。 11. **用链表模拟大整数加法运算** 将数字分解为链表的节点,每个节点代表一位数,然后按位进行加法运算,处理进位问题。 12. **单链表...

    西南科技大学软件技术期末考试题

    **7. 解决队列的假溢出问题** - **选项解析:** - 循环队列通过重新利用队列前端的空间来解决假溢出问题。 - **正确答案:B** **8. 二维数组的存储地址计算** - **选项解析:** - 当二维数组按行优先存储时,...

    算法数据结构

    2. **查找单链表的倒数第k个元素**:可以使用快慢指针,快指针先走k步,然后两个指针一起走,当快指针到达末尾时,慢指针即指向倒数第k个元素。 3. **找到单链表的中间元素**:同样使用快慢指针,快指针每次走两步...

    常见:算法面试题21

    判断两个单链表是否相交,且不带环。可以采用双指针法,分别从两个链表的头节点开始,快指针每次走两步,慢指针每次走一步,若两个链表相交,则会在某个点相遇。 8. **其他思维题**: 这些题目的解答涉及逻辑思维...

    数据结构与算法分析c++描述习题答案

    - 第7章 排序 - 第8章 不相交集合 - 第9章 图算法 - 第10章 算法设计技术 - 第11章 摊还分析 - 第12章 高级数据结构与实现 #### 详细知识点分析 1. **第2章 算法分析**: - **时间复杂度与空间复杂度**:...

    数据结构试题及答案

    在单链表中,访问第i个结点和在第i个结点后插入一个新结点的时间复杂度均为O(n),因为需要从头节点开始遍历到第i个结点。而删除第一个结点的时间复杂度为O(1),因为只需要改变头指针即可。 **6. 队列的判断** 队列...

Global site tag (gtag.js) - Google Analytics