单向链表求时间复杂度(训练营第 8 课)

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

题目

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

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





答题

假设链表分别为 A 和 B,对应长度为 m 和 n。

根据 A 和 B 是否 带环 以及是否有 交点,可以分下面几种情况:

  1. A 和 B 没有交点,则无论 A 和 B 是否有环;只要分别遍历两个链表,确定没有共同点即可。

  2. A 和 B 有交点,且 不带环;则 只要分别遍历两个链表,找到第一个交点即可完成。

  3. A 和 B 有交点,且带环;根据交点是否在环上,又可以分为 2 中情况:

  4. 如果交点不在环上,只要分别遍历两个链表,找到第一个交点即可完成

  5. 如果交点在环上,则 A 和 B 在环上的 入点 都可被认为是 合并点。



解题思路

  1. 定义 HashSetA 和 HashSetB 用来保存每个节点的引用或地址

  2. 遍历链表 A 的每个节点,并检查该节点是否已经在 HashSetA 里边

  • 假如 当前节点 已经在 HashSetA 里边,则说明链表 A 带环且入环节点为当前节点;保存当前入环节点并结束遍历

  • 假如 当前节点 不在 HashSetA 里边,则插入该节点到 HashSetA 里边。

  1. 遍历链表 B 的所有节点,并检查该节点是否可以在 HashSetA 里边找到

  • 假如可以找到,则说明两个链表有交叉点,且交叉点为当前节点(假如链表 A 带环,则交叉点也可以为链表 A 的入环点)

  • 假如没有找到,则继续检查该节点是否已经在 HashSetB 里边

  • 假如 当前节点 已经在 HashSetB 里边,则说明链表 B 带环且两个链表没有交叉点;结束遍历

  • 假如 当前节点 不在 HashSetB 里边,则插入该节点到 HashSetB 里边。

  1. 返回交叉点或者 null



时间复杂度

由于只要分别遍历一遍两个链表 A 和 B,所有时间复杂度为 O(max(m, n))

空间复杂度

需要两个 Hash 表来保存每个节点的引用或地址,所以空间复杂度为 O(max(m, n))

伪代码实现

Def HashSet setA; // 保存链表 A 的所有节点引用(地址)
Def HashSet setB; // 保存链表 B 的所有节点引用(地址)
def resutlNode = null;
def enterPointA = null; // 保存链表 A 的入环节点引用
def node = A.head;
while node != null;
if node is in setA; // 找到 A 环的入口点
enterPointA = node;
break;
else
setA.add(node);
end // if
end // while
node = B.head;
while node != null;
if node is in setA; // 找到交点
if enterPointA == null; // 不带环
resutlNode = node;
break;
else // 带环
resultNode = node; // 选择 B 的入口点作为合并点
// resultNode = enterPointA; // 选择 A 的入口点作为合并点
break;
end // if
else // 不是交点
if node is in setB; // 找到 B 环的入口点
resutlNode = null// 结束循环,没有交点
break
else
setB.add(node);
end // if
end // if
end // while
return resultNode;



用户头像

看山是山

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论

发布
暂无评论
单向链表求时间复杂度(训练营第 8 课)