极客时间架构师训练营 - week8 - 作业 1

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

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

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





思路:将其中的一个链表全部存入哈希表,然后遍历另外一个链表,如果之前的链表包含此元素,记录下此时位置,即可以判断两个链表存在合并的元素X。

package jjn;
import java.util.Objects;
import java.util.StringJoiner;
/**
* @author Jiang Jining
* @date 2020/7/29 21:54
*/
public class Node {
private Integer index;
private String value;
public Node() {
}
public Integer getIndex() {
return index;
}
public void setIndex(Integer index) {
this.index = index;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equals(value, node.value);
}
@Override
public int hashCode() {
return Objects.hash(value);
}
@Override
public String toString() {
return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
.add("index=" + index)
.add("value='" + value + "'")
.toString();
}
}



package jjn;
import java.util.*;
/**
* @author Jiang Jining
* @date 2020/7/29 21:54
*/
public class LinkListTest {
public static void main(String[] args) {
List<Node> listA = new LinkedList<>();
List<Node> listB = new LinkedList<>();
for (int i = 0; i < 10; i++) {
Node randomNode = getRandomNode(i);
listA.add(randomNode);
}
for (int i = 0; i < 15; i++) {
Node randomNode = getRandomNode(i);
listB.add(randomNode);
}
System.out.println("listA:");
listA.forEach(System.out::println);
System.out.println("listB:");
listB.forEach(System.out::println);
Node mergingNode = getMergingNode(listA, listB);
if (mergingNode == null) {
System.out.println("两个链表无合并");
} else {
System.out.println("合并的元素是:" + mergingNode);
}
}
private static Node getRandomNode(int index) {
Node node = new Node();
node.setIndex(index);
node.setValue((char) (Math.random() * 26 + 'A') + "");
return node;
}
private static Node getMergingNode(List<Node> listA, List<Node> listB) {
if (listA == null || listB == null) {
return null;
}
Set<Node> nodes = new HashSet<>(listA.size());
nodes.addAll(listA);
for (Node node : listB) {
if (nodes.contains(node)) {
return node;
}
}
return null;
}
}

请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。



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

jjn0703

关注

Java工程师/终身学习者 2018.03.26 加入

USTC硕士/健身健美爱好者/Java工程师.

评论

发布
暂无评论
极客时间架构师训练营 - week8 - 作业1