第 8 周 - 课后练习

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

题1

有两个单向链表(链表长度分别为m,n),这两具单向链表可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定这两个链表的头指针,在不修改链表的情况下,如何快速判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中x的元素。(请用伪代码描述算法,并给出时间、空间复杂度)。



Node : {

Object data();

Node next();

}

m = linkedListM.length;

n = linkedListN.length;

linkedListMap = {

m : linkedListM,

n : linkedListN

}

minLen = MIN(m,n);

maxLen = MAX(m,n);

shortLinkedList = linkedListMap[minLen];

longLinkedList = linkedListMap[maxLen];

//将短连接所有节点指针存入hasetset

Set<Node> shortLinkedListNodeSet = new HashSet();

for (each node in shortLinkedList){

shortLinkedListNodeSet.add(node);

}

//遍历长链表longLinkedList各节点指针地址是否在 shortLinkedListNodeSet 存在

{

//如果找到第一个返回节点对应的数据 x

}

//如果一直没有找到返回无交集



时间复杂度: O(2minLen+maxLen) ,空间复杂度:O(minLen)



用户头像

Dawn

关注

还未添加个人签名 2018.07.04 加入

还未添加个人简介

评论

发布
暂无评论
第8周-课后练习