极客时间 - 架构师一期 - 第八周作业

作业一：

（至少完成一个）

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

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



//有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。

// 现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

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

//时间复杂度：O(长链表长度+2*短链表长度) O(n)

public class JudgeMerge {

public static void main(String[] args) {

Node node1 = new Node("a", new Node("b", new Node("x", new Node("y", new Node("z", null)))));

Node node2 = new Node("d", new Node("e", new Node("f", new Node("x", new Node("y", new Node("z1", null))))));

int node1Length = listLength(node1);

int node2Length = listLength(node2);

Node result;

if (node1Length >= node2Length){

result = mergeable(node1, node1Length, node2, node2Length);

}else{

result = mergeable(node2, node2Length, node1, node1Length);

}

System.out.println("是否可以合并：" + (result != null) + ", nodeValue:" + result.getValue());

}



private static int listLength(Node node){

int i = 0;

while (node!=null){

node = node.getNextNode();

i++;

}

System.out.println(i);

return i;

}



private static Node mergeable(Node longNode, int longNodeLength, Node shortNode, int shortNodeLength){

//差几位移动几位

int i = longNodeLength - shortNodeLength;

while(i > 0){

longNode = longNode.nextNode;

i--;

}

System.out.println(longNode.getValue());

while(longNode.nextNode != null && shortNode.nextNode != null){

if(longNode.getValue().equals(shortNode.getValue()) ){

return longNode;

}

longNode = longNode.getNextNode();

shortNode = shortNode.getNextNode();

}

return null;

}



}



class Node{

String value;

Node nextNode;



public Node(String value, Node nextNode) {

this.value = value;

this.nextNode = nextNode;

}



public String getValue() {

return value;

}



public void setValue(String value) {

this.value = value;

}



public Node getNextNode() {

return nextNode;

}



public void setNextNode(Node nextNode) {

this.nextNode = nextNode;

}

}



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