第八周作业 1

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

如果合并，找到合并的元素，也就是图中的 x 元素。

参考 Leetcode 160 题。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions

两种方法：

• 把一个链表的 node 数据全部放到 set 集合中，遍历第二个列表中的 node 是否存在 set 集合中。

时间复杂度为 O(m+n), 空间复杂度为 O(m)。

• 定义两个指针分别从链表 1、链表 2 头节点出发，都走完两个链表的所有节点，如果两个链表有相交点，则它们必相交与合并的节点。链表 1 到相交点 x，链表 2 到相交点 y，合并共同节点 k。则链表 1 走的距离为 x+k+y；链表 2 走的距离为 y+k+x；它们刚好在合并点相交。

时间复杂度为 O(m+n)，空间复杂度为 O(1)。

public class LeetCode_160 {  // 方法1，通过集合判断	public ListNode getIntersectionNodeV1(ListNode headA, ListNode headB) {		Set<ListNode> set = new HashSet<>();    // 遍历链表A，把所有节点存放在集合中		while (headA != null) {			set.add(headA);			headA = headA.next;		}    // 遍历链表B，判断节点是否存在集合中。如存在则是它们的合并点		while (headB != null) {			if (set.contains(headB)) {				return headB;			}			headB = headB.next;		}		return null;	}	  // 方法2，如果链表相交，两个指针交叉分别走相同的路径的最后应该在同一个点。	public ListNode getIntersectionNodeV2(ListNode headA, ListNode headB) {		ListNode node1 = headA, node2 = headB;		while (node1 != node2) {			node1 = node1 != null ? node1.next:headB;			node2 = node2 != null ? node2.next:headA;		}		return node1;	}}

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

HDFS 架构图：

HDFS 通过把数据存分块存放到不同的服务器来解决单机中数据的读写能力和提高数据的高可用能力。

NameNode 节点知道所有的数据存放的节点信息，DataNodes 节点是不同的存放数据的节点，默认 1 份数据会被存放 3 个副本，并存放到不同的机架。NameNode 节点通过 DataNodes 节点的主动心跳检测来判定 DataNodes 节点是否可用，如果检测到 DataNodes 节点不可用，将会通知有相同数据的节点复制不可用节点的数据到其他地方，保持数据节点副本数，具体逻辑如下图：