写点什么

第八周课后作业

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



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

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





先计算两个链表的长度m、n,找到那个较长的链表(longList)

让 longList 的头指针向后移动 abs(m-n) 个节点;这样长、短链表就一样长了

然后挨个比较两个链表的头指针,如果一样则返回该节点;不一样则头指针分别往后移动一位

循环步骤 3,直到链表遍历结束



时间复杂度 O(n)



空间复杂度 O(1)

public boolean listMeet(LinkedList shorts, LinkedList longs){



int temp = longs.size() - shorts.size();



// 去掉长链表的头,让两个链表一样长

while (temp>0){

longs.remove(0);

temp --;

}



// 从头开始比较两个链表,看是否相同,相同点就是合并点

for(int i=0; i<longs.size(); i++){

if(shorts.get(i).equals(longs.get(i))){



// 相遇点

LinkedList meetNode = (LinkedList)shorts.get(i);

return true;

}

}

// 没有共同点

return false;

}



用户头像

晨光

关注

还未添加个人签名 2019.08.13 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:43
回复
没有更多了
第八周课后作业