架构师第 8 周作业

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

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

【A】主要想法就是，先把两个链表节点分别压入栈，然后，比较，如果两个栈顶不一致，则，没有并集，如果栈顶一致，则有并集，只需要 pop 出一致的，第一次遇到不一致的，它的 next 就是合并点

def get_merge_node(head1, head2):

if head1 == None or head2 == None:

return None

if head1 == head2:

return head1

#convert link to stack

node_stack1 = get_node_stack(head1)

node_stack2 = get_node_stack(head2)

if not node_stack1.pop() == node_stack2.pop():

return None

else:

repeat = min(len(node_stack1),len(node_stack2))

for i in range(0, repeat):

node1 = node_stack1.pop()

node2 = node_stack2.pop()

if not node1.value == node2.value:

break

return node1.next

def get_node_stack(head):

node_stack = []

link_node = head

if head == None:

return node_stack

while True:

#push node to stack

node_stack.append(link_node)

if link_node.next == None:

break

link_node = link_node.next

return node_stack

class node():

def __init__(self, value):

self.value = value

self.next = None

def gettestdata(m,n,merge_len=0):

head1 = None

head2 = None

head1 = node(0)

prev_node1 = head1

for i in range(1,m-merge_len):

link_node = node(i)

prevnode1.next = linknode

prevnode1 = linknode

head2 = node(m+n)

prev_node2 = head2

for i in range(m+n+1,m+n+n-merge_len):

link_node = node(i)

prevnode2.next = linknode

prevnode2 = linknode

for i in range(m-merge_len,m):

link_node = node(i)

prevnode2.next = linknode

prevnode1.next = linknode

prevnode1 = linknode

prevnode2 = linknode

return (head1, head2)

if name == 'main':

print("no merge")

(head1, head2) = gettestdata(10, 15, 0)

link_node = head1

while True:

print(link_node.value)

if link_node.next == None:

break

linknode = linknode.next

link_node = head2

while True:

print(link_node.value)

if link_node.next == None:

break

linknode = linknode.next

mergenode = getmerge_node(head1, head2)

print(merge_node)

print("merge at 6")

(head1, head2) = gettestdata(10, 15, 6)

print('list1')

link_node = head1

while True:

print(link_node.value)

if link_node.next == None:

break

linknode = linknode.next

link_node = head2

print('list2')

while True:

print(link_node.value)

if link_node.next == None:

break

linknode = linknode.next

mergenode = getmerge_node(head1, head2)

print(merge_node.value)

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

hdfs datanode 宕机的时序图