2 个单向列表寻找合并点

用户头像
俊俊哥
关注
发布于: 2020 年 08 月 01 日
2个单向列表寻找合并点

问题

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。





解决方案

第一种方案,最简单的原始方案:直接迭代链表m,并比对链表n的每一个原始。

这种方案的复杂度是O(m*n),空间复杂度为O(m+n)



第二种方案,使用一个hash结构存储m,然后迭代n。

这种方案的复杂度是O(m+n),空间复杂度为O(2m+n)



第三种方案,是从leetcode看到的,很精彩:

我们使用两个指针 node1,node2 分别指向两个链表 m,n 的头结点,然后同时分别逐结点遍历,当 node1 到达链表 m 的末尾时,重新定位到链表 n 的头结点;当 node2 到达链表 n 的末尾时,重新定位到链表 m 的头结点。

这样,当它们相遇时,所指向的结点就是第一个公共结点。

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
node1, node2 = headA, headB
while node1 != node2:
node1 = node1.next if node1 else headB
node2 = node2.next if node2 else headA

return node1

本周总结

数据结构,在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更具有深厚的背景。



程序是利用计算机的告诉运算能力来协助我们处理问题的。而一台计算机的CPU运算能力是有限的,只会机械的接收程序的指令,所以算法的优劣决定了程序设计水平的上限。



当然,我们现在其实很少直面算法的场景,这是因为有人在为我们负重前行,作为一个架构师,是必须要了解一些算法的基本知识的。



还有就是TCP/IP分层模型的分层和功能的讲解、NIO、数据库基本模型,算是一次复习,温故知新。

发布于: 2020 年 08 月 01 日 阅读数: 34
用户头像

俊俊哥

关注

架构是平衡的艺术 2013.06.01 加入

还未添加个人简介

评论

发布
暂无评论
2个单向列表寻找合并点