第八周作业

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

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



方法一

// 比较链表的长度,找到短的链表

lowsize = head1.getLength() > head2.getLength() ? head2.getLength(): head1.getLength();

if ( lowsize = head1.getLength()){

shead = head1 ;

lhead = head2 ;

}else{

shead = head2 ;

lhead = head1 ;

}

// 定义数组做hash表

ptr store[lowsize]

// 遍历短的链表，按地址值映射到store,要保证没有冲突

sptr=shead;

while(sptr != null){

store[hash[sptr]] = sptr;

sptr = sptr.getNext();

}

//遍历长链表，在store查询是否存在相同的ptr值

lprt=lhead

while(lptr != null){

if (store[hash(lptr)] == lptr ){

break ;

}

lptr = lptr.getNext();

}

if (lptr!= null){

return lptr.getValue();

}

时间复杂度为 O(n),空间复杂度也为O(n)



方法二

// 比较两个链表的长度，确定长短链表

largesize = head1.getLength() > head2.getLength() ? head1.getLength():head2.getLength() ;

smallsize = head1.getLength() > head2.getLength() ? head2.getLength():head1.getLength() ;

if ( smallsize == head1.getLength() )

{

sptr = head1 ;

lptr = head2 ;

}

else

{

sptr = head2 ;

lptr = head1 ;

}

// 遍历长链表

while ( largesize != smallsize)

{

lptr = lptr.getNext();

largesize = largesize - 1;

}

// 长、短链表同时遍历，确定有无交集

while (lptr != null && sptr != null)

{

if (lprt == sptr){

break;

}

lptr = lptr.getNext();

sptr = sptr.getNext();

}



if (lptr != null)

{

return lptr.getValue();

}

时间复杂度为 O(n),空间复杂度也为O(1)



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