架构师训练营第 8 周作业 算法与数据结构
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
方法一
最简单的方法就是在遍历其中一个链表,并在遍历其每个节点的时候遍历一遍另一个链表,判断该节点是否在另一个链表中。这个算法的时间复杂度为O(mn),空间复杂度为O(1),虽然简单但时间复杂度最高。
方法二
由于单链表的每个节点只有一个next,因此相交后所有节点必然都重合,可以分别将两个链表压入两个栈,如果压完后两个栈顶不同,则说明两个链表没有相交,如果相同,则同时出栈,直到两个栈顶不同,那么上一个出栈的节点就是相交点。该算法的时间复杂度是O(n)(假设n大于m),空间复杂度为O(m+n)。
方法三
如果两个链表长度相同,那么同时开始遍历,在相交处一定会相遇,如果两个链表长度不同,则只要让长的先走几步,走到两个链表剩余长度相同,那么就可以开始同时遍历。该算法时间复杂度O(n)(假设n大于m),空间复杂度O(1)。这个算法的前提是已知两个链表的长度。
方法四
由于链表中每个节点的地址是确定且唯一的,因此可以对其中一个链表中每个节点的地址计算哈希值,存入哈希表,然后再对另一个链表中的每个节点的地址依次计算哈希值,只要这个值已经在哈希表里,则说明当前节点就是相交点。该算法时间复杂度为O(m+n),空间复杂度为O(n)(假设n大于m)。
上述四种算法都只适用于链表无环的情况,下面分析一下链表有环的情况。
如果链表有环,则环一定是两个链表共用的,因此使用判断链表是否有环的算法,如果得出的结果是只有一个链表有环,那么两个链表一定不相交。如果两个链表都有环,那么相交点有两种情况:在环外相交和在环内相交。
在环外相交的情况,由于环是共用的,因此不看环的话就跟上面所讲的Y型相交是一样的了。因此可以先在其中一个链表上使用环算法得到环入口,然后再从该链表开头使用上述方法三,如果在到达环入口之前找到了相交点,则返回相交点,否则说明是环内相交。
环内相交的情况,只要返回任意一个链表的环入口节点即可。
评论