单向链表合并问题

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

0. 问题

考虑这样一个问题:

如果有两个单向链表(链表长度分别为m,n),已知两个链表的头指针。如何判断两个链表是否合并?如果合并,找到开始合并的元素。



1. 作答

思路一

如果两个链表合并,开始合并的元素一定在两个链表都存在且相同。根据这个思路,循环两个链表,找有没有相同的元素,有相同元素就说明链表合并,没有就说明没有合并。

  • 伪代码形式:

//已知m、n的链表的头指针
Node mhead=new Node();
Node nhead=new Node();
/**
* 传入两个链表的头结点,如果有合并返回合并的节点,否则返回空。
*/
public Node findMergeNode(Node mhead,Node nhead){
//循环的偏移量
Node moffset=mhead;
Node noffset=nhead;
while(moffset!=null){
while(noffset!=null){
if(moffset==noffset){
return moffset;
}
noffset=noffset.next;
}
moffset=moffset.next;
}
return null;
}

注:用==判断是判断两个链表节点的内存地址(指针)是否相同,不是Node中的值是否相同。



  • 时间复杂度:因为有两次嵌套循环,时间复杂度为O(m)×O(n)即O(n²)

  • 空间复杂度:除了两个入参列表外没有申请新的空间,空间复杂度为O(1)



思路二

基于思路一,我们还是找两个链表都存在的元素。不过我们可以使用一个set链表的存储元素,首先遍历第一个链表,将元素存入set。然后遍历第二个链表,判断值是否在存在在set中。存在的元素就是开始合并元素。这个思路使用了空间换时间思想。

  • 伪代码形式:

//已知m、n的链表的头指针
Node mhead=new Node();
Node nhead=new Node();
/**
* 传入两个链表的头结点,如果有合并返回合并的节点,否则返回空。
*/
public Node findMergeNode(Node mhead,Node nhead){
//循环的偏移量
Node moffset=mhead;
Node noffset=nhead;
Set<Node> set=new HashSet<Node>();
while(moffset!=null){
set.add(moffset);
moffset=moffset.next;
}
while(noffset!=null){
if(!set.add(noffset)){
//找到重复值
return noffset;
}
noffset=noffset.next;
}
return null;
}

注:

  • 实际代码需要关注Node类中equals方法,使set能正确判断相等。

  • 使用set而不用list等容器,因为前者查找某个数据的时间复杂度为O(1)后者为O(n).



  • 时间复杂度:有两次循环,虽然循环内有一个set的add操作,但是add的时间复杂度为O(1)。所以算法整体的时间复杂度为O(m)+O(n)即O(n)

  • 空间复杂度:引入了新的set存储链表元素,空间复杂度为O(m)+O(n)即O(n)

总结:

  • 思路一时间复杂度O(n²)大于思路二时间复杂度O(n)

  • 思路一空间复杂度O(1)小于思路二空间复杂度O(n)

  • 两者互为时间-空间互换的思想



2. 链表成环

以上问题是建立自两个链表都不成环的假设下,如果两个链表中某个链表成环,以上两段算法程序都会进入“死循环”阶段。下篇文章我们讨论链表成环问题。并进一步改进我们的的代码。



发布于: 2020 年 07 月 29 日 阅读数: 39
用户头像

Jerry Tse

关注

还未添加个人签名 2018.11.02 加入

还未添加个人简介

评论

发布
暂无评论
单向链表合并问题