架构师训练营第 1 期 week8
发布于: 2020 年 11 月 15 日
1、有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
import java.util.HashMap;import java.util.Map;
public class LinkedMerge { public static String merge(Node node1,Node node2){ Map<String,String> nextMap = new HashMap<String,String>(); Node currentNode1 = node1; while(currentNode1!=null){ //记录每个节点的下一个节点 if(currentNode1.next!=null) { nextMap.put(currentNode1.date,currentNode1.next.date); }else{ //如果下一个节点不存在，则说明该节点是最后一个 nextMap.put(currentNode1.date,null); } currentNode1 = currentNode1.next; } Node currentNode2 = node2; String result =""; String node1Next=""; while(currentNode2!=null){ //判断result是否有值，如果有则说明已经找到可以合并的元素，现在处于往后比较值是否一致的阶段 if(!"".equals(result)){ if(node1Next==null) break; if(node1Next.equals(currentNode2.date)){ node1Next = nextMap.get(node1Next); currentNode2 = currentNode2.next; continue; }else{ //重新开始统计 result = ""; node1Next=""; } } //如果result为空 开始找相同节点 node1中包含该节点 if(nextMap.containsKey(currentNode2.date)){ result = currentNode2.date; node1Next = nextMap.get(currentNode2.date); } currentNode2 = currentNode2.next; } return result; }
class Node{ String date; Node next; Node(String date,Node next){ this.date = date; this.next = next; } }
public static void main(String[] args) { LinkedMerge linkedMerge = new LinkedMerge(); Node node1 = linkedMerge.new Node("1",linkedMerge.new Node("2",linkedMerge.new Node("3",linkedMerge.new Node("4",null)))); Node node2 = linkedMerge.new Node("2",linkedMerge.new Node("3",linkedMerge.new Node("4",null))); String merge = merge(node1, node2); System.out.println("".equals(merge)?"没有可以合并的元素":("合并点:"+merge));
node1 = linkedMerge.new Node("1",linkedMerge.new Node("2",linkedMerge.new Node("3",null))); node2 = linkedMerge.new Node("2",linkedMerge.new Node("3",linkedMerge.new Node("4",null))); merge = merge(node1, node2); System.out.println("".equals(merge)?"没有可以合并的元素":("合并点:"+merge));
node1 = linkedMerge.new Node("1",linkedMerge.new Node("2",linkedMerge.new Node("3",null))); node2 = linkedMerge.new Node("2",linkedMerge.new Node("5",linkedMerge.new Node("6",null))); merge = merge(node1, node2); System.out.println("".equals(merge)?"没有可以合并的元素":("合并点:"+merge));
}}复制代码
测试结果：
有相同子串，并且直到结尾，两个链表都一致，合并点:2
有相同子串，并且一个链表到结尾，另一个链表会额外多一些元素的情况，合并点:2
有相同值但是后面字串不完全相同时，没有可以合并的元素
时间复杂度：m+n，因为使用了字典项存储，暂时不支持有重复值的链表
2、请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图
划线
评论
复制
发布于: 2020 年 11 月 15 日阅读数: 33
张建亮
关注
还未添加个人签名 2020.07.29 加入
还未添加个人简介
评论