第八周架构师训练营作业

用户头像
子豪sirius
关注
发布于: 2020 年 07 月 27 日

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

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



方法一:

遍历其中一个链表,对于上面的每一个节点,再遍历另一个链表,如果有相同,返回。伪代码如下:

pA <- Head(ListA)
while pA != null
pB <- Head(ListB)
while (pB != null)
if Node(pA) = Node(pB)
return Node(pA)
pB <- Next(pB)
pA <- Next(pA)
return null

时间复杂度为O(mn),空间复杂度为O(1)(没有额外的空间)



方法二:

两个指针同时遍历两个链表,当一个指针到达链表末尾的时候,指针指向另一个链表头,直到有相同的节点或者都到达末尾为止。伪代码如下:

pA <- Head(ListA)
pB <- Head(ListB)
while pA != null AND pB != null
if Node(pA) = Node(pB)
return Node(pA)
pA <- Next(pA)
pB <- Next(pB)
if Node(pA) = null
pA <- Head(ListB)
if Node(pB) = null
pB <- Head(ListA)
return null

时间复杂度为O(m+n),空间复杂付为O(1)



方法三:

计算两个链表的长度,较长的链表先前进两个链表长度之差的步数,再两个链表同时遍历比较。伪代码如下:

p1 <- Head(ListA)
p2 <- Head(ListB)
len1 <- Length(ListA)
len2 <- Length(ListB)
delta <- len1 - len2
if len1 < len2
delta <- len2 - len1
p1 <- Head(ListB)
p2 <- Head(ListA)
for delta to 0
p1 <- Next(p1)
while p1 != null AND p2 != null
if Node(p1) = Node(p2)
return Node(p1)
p1 <- Next(p1)
p2 <- Next(p2)
return null

时间复杂度为O(max(m,n)),空间复杂度为O(1)

用户头像

子豪sirius

关注

还未添加个人签名 2018.05.03 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
请加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 28 日 18:02
回复
没有更多了
第八周架构师训练营作业