写点什么

两个单向链表是否可以合并

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



public Object getMergeElement(Node m,Node n) {
// 获取两个链表的最后一个元素
Node tmpm;
Node tmpn;
Node orgM = m;
Node orgN = n;
int mLength = 0;
int nLength = 0;
while(m.nextNode != null) {
tmpm = m;
m = m.nextNode;
mLength++;
}
while(n.nextNode != null) {
tmpn = n;
n = n.nextNode;
nLength++;
}
// 如果两个链表的最后一个元素不相等,则两个链表不能合并
if(tmpm.equmls(tmpn)) {
return null;
}
// 如果两个链表最后一个元素相等,则两个链表可以合并
// 找出长度较长的链表,从长度差位置开始寻找合并点
m = orgM;
n = orgN;
if(mLength > nLength) {
for(int i = 0; i < mLength-nLength; i++) {
m = m.nextNode;
}
for(int j = 0; j < nLength; j++) {
if(m.equmls(n)) {
return m;
}
m = m.nextNode;
n = n.nextNode;
}
} else {
for(int i = 0; i < nLength-mLength; i++) {
n = n.nextNode;
}
for(int j = 0; j < mLength; j++) {
if(n.equmls(m)) {
return n;
}
m = m.nextNode;
n = n.nextNode;
}
}
}

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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

用户头像

潜默闻雨

关注

还未添加个人签名 2018.11.23 加入

还未添加个人简介

评论

发布
暂无评论
两个单向链表是否可以合并