判断链表是否合并

用户头像
elfkingw
关注
发布于: 2020 年 07 月 29 日
判断链表是否合并

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

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





思路:

1.两个链表(长度分别为m和n)中找出长度短的连表

2.遍历长度短的连表,短的连表从index=0开始 ,长的连表从index=abs(m-n)开始

3.比较两个连表中的值是否相等,

时间复杂度为O(短l连表的长度),空间复杂度没有使用多于的空间

代码如下:

public String findMergeNode(List<String> aList, List<String> bList) {
List<String> longList;
List<String> shortList;
int offset = 0;
String mergeNode = null;
if (aList.size() > bList.size()) {
longList = aList;
shortList = bList;
offset = aList.size() - bList.size();
} else {
longList = bList;
shortList = aList;
offset = bList.size() - aList.size();
}
for (int i = 0; i < longList.size() - offset; i++) {
String a = shortList.get(i);
String b = longList.get(i + offset);
if (a == b) {
if (mergeNode == null) {
mergeNode = a;
}
} else {
mergeNode = null;
}
}
return mergeNode;
}



用户头像

elfkingw

关注

还未添加个人签名 2018.02.04 加入

还未添加个人简介

评论

发布
暂无评论
判断链表是否合并