写点什么

第八周作业

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

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

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

分别循环两个链表,

List<Object> a

List<Object> b

Object lastElementA = a.get(a.getSize() - 1);

Object lastElementB = b.get(b.getSize() - 1);

如果有合并,那么最后一个元素必定相同,所以 lastElementA == lastElementB 为 true,否则没有合并。

取合并元素,比较两个链表的长度,a.getSize() - b.getSize() =c,再让较长的链表先循环 c 个元素,此时两个链表长度一致。再同时开始循环,比较第一个相同的节点

时间复杂度是 O(A+B),空间复杂度是 O(n)

用户头像

方堃

关注

还未添加个人签名 2019.02.11 加入

还未添加个人简介

评论 (1 条评论)

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