week8 作业 1

用户头像
关注
发布于: 2020 年 07 月 29 日

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

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





分析:由于是单向链表,如果这两个单向链表在某个元素合并,则这个合并的元素后的每个元素都是合并的。



伪代码如下:

由于已知这两个链表的长度,则可以判断出两个链表的长短,假设这两个链表分表为L1和L2,长度分别为m和n,定义两个指针p1和p2

if L1为空或L2为空:

return NULL

if m >= n:

p1 指向L1的头结点

p2指向L2的头结点

else:

p1指向L2的头结点

p2指向L1的头结点



diff = abs(m - n)

遍历长链表的前diff步

for(int i=0; i<diff; i++){

p1 = p1->next;

}

遍历后续的链表节点

while(p1 != p2)

{

p1 = p1->next;

p2 = p2->next

}

返回p1

时间复杂度:o(n+m)

空间复杂度:o(1)

发布于: 2020 年 07 月 29 日 阅读数: 4
用户头像

关注

还未添加个人签名 2019.04.12 加入

还未添加个人简介

评论

发布
暂无评论
week8作业1