题 1 判断单向链表是否合并

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

请用代码（或伪代码）描述算法，并给出时间复杂度

答：分析过程如下：

单向链表，说明每个节点的后续节点唯一。分有环与无环讨论：

1. 若两单向链表 pHead1, pHead2 都无环，则相交的模式为 Y 形：

2. 遍历 pHead1 求长度 len1；遍历 pHead2 求长度 len2

3. 若 pHead1 的尾部==pHead2 的尾部，则返回相交，且交点为尾部

4. 取 maxlen(len1, len2), 从长的链表的首部步进长度 len( abs(len1-len2))

5. 每一步都步进 pHead1，pHead2 一次，判断目标节点是否相同。如是，则返回相交。

6. 否则返回不相交。

7. 若有环（通过快慢指针判断: pSlow 每次步进 1，pFast 每次步进 2, 若有环则会相交），有 3 种情况：

8. 交点在环开始之前：以无环模式运行

9. 交点在环入口处：以无环模式运行

10. 交点在环内：找到链表一和链表二的环入口节点，各自的环入口节点即为各自第一次相交的节点

时间复杂度 O(n).

题 2 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图

每 3 秒，每个 DataNode 给 NameNode 发送心跳消息，如果 NameNode 在 10 分钟内一直没有收到某个 DataNode 的心跳，就开始启动数据块复制给其他正常 DataNode 节点: