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

#伪代码。思路：1、链表入栈；2、同时出栈判断是否可以合并；
//定义两个链表
Node<T> nodeA;//链表1
Node<T> nodeB;//链表2
//定义两个栈
Stack stackA;
Stack stackB;
//合并元素的值x
Node<T> mergeNode=null;
//遍历链表A入栈A
stackA.push(nodeA);
while(nodeA.next!=null)
{
	stackA.push(nodeA.next);
  nodeA=nodeA.next；
}
//遍历链表B入栈B
stackB.push(nodeB);
while(nodeB.next!=null)
{
	stackB.push(nodeB.next);
  nodeB=nodeB.next；
}
//两个栈同时出栈，判断节点的值是否相同，如果相同则合并
while(!stackA.isEmpty()&&!stacbB.isEmpty())
{
	Node<T> a=stackA.pop();
  Node<T> b=stackB.pop();
	if(a==b) mergeNode=a;  //如果值相同则存在合并的值
  else break;   //如果值不相同则直接跳出不再合并
}
return mergeNode;  //如果result为null则链表不能合并，如果result不为null则是第一个合并的值

时间复杂度为3个循环，O(n)=n



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



三、根据当周学习情况，完成一篇学习总结

8.1 文件与硬盘 I/O：如何把硬盘的读写速度提高十万倍？

提高速度的通用模式就是：

方法一：提高单个处理节点的能力，如硬盘从机械旋转改电子元件处理；

方法二：让多个处理节点替代一个处理节点，如RAID，HDFS等。但是必须时刻考虑失效的情况，以及故障的恢复。



8.2 常见数据结构与Hash表原理分析

数组+链表 是最基础的存储结构。

• 数组适用固定长度，快速定位，增删节点慢

• 链表适用非固定长度，定位慢，增删节点快

hash表的数据结构也是利用数组+链表的方式，提高访问速度。



通过队列搜索来解决最短路径、最有钱人等算法。算法模板如下：

1. 入队列，并记录谁让我进来的（以便于反向找路径）

2. 出队列，计算值。如果非终点则将直接连接的节点入队列

3. 重复 1



8.3 红黑树原理与性能特性

数据的查找演化：最求效率，放弃空间资源

• 二叉树

• 平衡二叉树，左右深度差值不超过1，查找快，增加快删慢

• 红黑树，左右红黑节点数量平衡，查找快，增加删除都快，算法复杂

• 跳表替代红黑树。多级链表，查找较快，增删快，算法简单，但存储多

在不同的环境不同的用法



8.4 经典算法

穷举、递归、贪心、动态规划。

动态规划可用二维表解



8.5 网络通信基本原理与性能优化

http1.0 每次三次握手，四次挥手，开销大

http1.1 一次连接，顺序发送内容。开多个连接提高并发，就成了http1.0 了

http2 一次连接，可同时发送内容，但按顺序处理

http3 UDP发送



8.6 非阻塞网络I/O

todo: 在目前工作中接触较少，待加强。。。