判断两个链表是否合并

用户头像
Z冰红茶
关注
发布于: 7 小时前

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

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





分析:如图所示,链表重合的条件是链表后半部分一样,即交叉节点开始,之后的节点都一样

1、两个链表长度不同,没有重合

2、两个量表长度一样,没有重合

3、两个链表长度不同,有重合

4、两个链表长度一样,有重合

思路:所以最多把两个链表遍历一遍就可以知道链表是否有重合

最简单的方式是遍历其中一个链表,并在循环冲遍历另外一个链表,时间复杂度是O(mn);

根据链表重合条件,如果有重合肯定是在链表尾部,所以只需要遍历(假设m大于n)(m-n)到m是否一样即可,时间复杂度为O(n)

还有一种简便方式,依次遍历两个链表,a先遍历链表1,然后遍历链表2,b先遍历链表2,然后遍历链表1,ab都是遍历了(m+n),时间复杂度O(m+n)

public static <T> T getMerge(Node<T> link1, Node<T> link2){
Node<T> current1 = link1;//current1先遍历链表1再遍历链表2
Node<T> current2 = link2;//current2先遍历链表2再遍历链表1
// 找到共同节点,或分别遍历完成,结束
while(!current1.value.equals(current2.value)&&(current1.next!=null && current2.next!=null)){
if(current1.next == null){
current1 = link2;
}else{
current1 = current1.next;
}
if(current2.next == null){
current2 = link1;
}else{
current2 = current2.next;
}
}
if(current1.value.equals(current2.value)){// 找到共同节点
return current1.value;
}else{// 遍历结束也没有找到共同节点
return null;
}
}
public static class Node<T>{
T value;
Node<T> next;
Node(T value){
this.value = value;
}
}

测试

@Test
public void getMerge() {
/**
* a->b->c->x->y->z
* d->e->f->x->y->z
* 返回x
*/
MergeOfLinkList.Node<String> link1 = createList(new String[]{"a","b","c","x","y","z"});
MergeOfLinkList.Node<String> link2 = createList(new String[]{"d","e","f","x","y","z"});
assertEquals("x", MergeOfLinkList.getMerge(link1, link2));
/**
* a->b->c->x->y->z
* d->e->f->g
* 返回 null
*/
MergeOfLinkList.Node<String> link3 = createList(new String[]{"d","e","f","g"});
assertNull(MergeOfLinkList.getMerge(link1, link3));
}

测试结果

最多只需要遍历m+n次,所以时间复杂度为O(m+n)

引入了两个Node变量,所以空间复杂为O(m+n)



发布于: 7 小时前 阅读数: 4
用户头像

Z冰红茶

关注

还未添加个人签名 2018.09.17 加入

还未添加个人简介

评论

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