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 的头结点。
这样,当它们相遇时,所指向的结点就是第一个公共结点。
本周总结
数据结构,在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更具有深厚的背景。
程序是利用计算机的告诉运算能力来协助我们处理问题的。而一台计算机的CPU运算能力是有限的,只会机械的接收程序的指令,所以算法的优劣决定了程序设计水平的上限。
当然,我们现在其实很少直面算法的场景,这是因为有人在为我们负重前行,作为一个架构师,是必须要了解一些算法的基本知识的。
还有就是TCP/IP分层模型的分层和功能的讲解、NIO、数据库基本模型,算是一次复习,温故知新。
版权声明: 本文为 InfoQ 作者【俊俊哥】的原创文章。
原文链接:【http://xie.infoq.cn/article/df834b4d47421339a55e6f801】。文章转载请联系作者。
评论