写点什么

【架构师训练营 - week8 -1】作业

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

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

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



思路:

假设 链表 1 未相交段为 A , 链表 2 未相交段为 B,相交段为 C

则 A+B=B+A

同时位移链表 1 和链表二头指针,当遇到 next 为空时,链表 1 指针指向链表 2 头节点,链表 2 指针指向链表 1 头节点,当两个节点值相等即为相交节点。


public Integer mergeNode(Node head1,Node head2){
Node node1 = head1;
Node node2 = head2;
int len = node1.length()+node2.length();
while(len>0)){
if(node1 == null){
node1 = head2;
}
if(node2 == null){
node2 = head1;
}
node1 = node1.next();
node2 = node2.next();
if(node1.value == node2.value){
return node1.value;
}
}
return null;
}
复制代码


用户头像

早睡早起

关注

还未添加个人签名 2019.09.05 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营 - week8 -1】作业