极客大学架构师训练营 数据结构与算法 分布式数据库 Hadoop 第八次作业

用户头像
John(易筋)
关注
发布于: 2020 年 07 月 29 日

链表算法

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

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

解题思路

如果有汇合点,那么后面的个数肯定是一样的。所以先把长链表的往前移动,跟短链表一样长后,再挨个比较。如果找到Node对象相等说明是一样的,返回该对象;否则返回Null。

时间复杂度为 O(n), 其中n为链表较长的。

空间复杂度为 O(n), 空间就是存储链表的数据。



package linkedlist;
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class FindCommonNode {
public ListNode findCommondNode(ListNode nodeM, ListNode nodeN, int m, int n) {
boolean isMBigThenN = m > n;
ListNode smallNode = isMBigThenN ? nodeN : nodeM;
ListNode bigNode = isMBigThenN ? nodeM : nodeN;
int gap = Math.abs(m - n);
while (gap > 0) {
bigNode = bigNode.next;
}
while (bigNode != null) {
if (bigNode == smallNode) {
return bigNode;
}
bigNode = bigNode.next;
smallNode = smallNode.next;
}
return null;
}
}



DataNode 时序图

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

上图为HDFS的架构,当DataNodes节点宕机时,因为该节点的数据在其它节点上有副本,所以可以将该节点的数据复制一份到另一个节点上,保证系统高可用。副本的配置存储在NameNode上,所以迁移逻辑需要由其控制。



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

John(易筋)

关注

问渠那得清如许?为有源头活水来 2018.07.17 加入

工作10+年,架构师,曾经阿里巴巴资深无线开发,汇丰银行架构师/专家。开发过日活过亿的淘宝Taobao App,擅长架构、算法、数据结构、设计模式、iOS、Java Spring Boot。易筋为阿里巴巴花名。

评论

发布
暂无评论
极客大学架构师训练营 数据结构与算法 分布式数据库 Hadoop 第八次作业