架构学习第 8 周作业

以下两题，至少完成一道

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

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





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



作业一

准备

伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。 介于自然语言与编程语言之间。常用的伪代码如下：

伪代码 含义 对应c++代码

← 赋值 =

= 比较 ==

≠ 不等于 ！=

≤ 小于等于 <=

≥ 大于等于 >=

for i←1 to n do for 循环 for(i=1;i⇐n;i++){}

for i←n downto 1 do for 循环 for(i=n;i>=1;i–){}

while i<n do while循环 while(i<n){}

do while i<n do while 循环 do {} while(i<n)

repeat until i<n repeat 循环

if i<n else if 条件判断 if(i<n){} else {}

A[0..n-1] 数组定义 int A[n]

A[i] 数组引用 数组引用

SubFun() 函数调用 SubFun()



程序伪代码：

p ← L1.head

visited ← new Set()

while p ≠ NULL do

visited.insert(p1)

p ← p.next()



p ← L2.head

while p ≠ NULL do

if visited.has(p)

return p

p ← p.next()

return NULL



时间复杂度O（m+n）, 空间复杂度O（m）