第八周课后作业
发布于: 2020 年 07 月 27 日
作业一：
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
大概思路是：从两个链表的后面往前来对比查找，遇到不相等的两个节点就停止查找，然后看前一个节点是否相等，相等则有交叉。
核心代码
public static void main(String[] args) { //初始化测试数据，没考虑空链表 //initLists();
int minLength = Math.min(mListLength, nListLength); int maxLength = Math.max(mListLength, nListLength); ListNode mergedNode = null; ListNode mListCompareNode; ListNode nListCompareNode; int mListCompareIndex; int nListCompareIndex;
//从后往前取 for (int indexFromLast = 0; indexFromLast < minLength; indexFromLast++) { mListCompareIndex = mListLength - indexFromLast - 1; nListCompareIndex = nListLength - indexFromLast - 1; mListCompareNode = mListFirstNode; nListCompareNode = nListFirstNode;
//由于是单向链表，所以需要从头部开始遍历 for (int i = 1; i < maxLength - indexFromLast;i++) { if (i <= nListCompareIndex) { nListCompareNode = nListCompareNode.getNext(); } if (i <= mListCompareIndex) { mListCompareNode = mListCompareNode.getNext(); } }
//发现节点不相等，则停止查找。相等则继续往前查找 if (nListCompareNode.equals(mListCompareNode)) { mergedNode = nListCompareNode; } else { break; } }
//判断是否有交叉 System.out.println("是否有合并: " + Objects.nonNull(mergedNode) + " 合并的元素：" + mergedNode); }复制代码
由于用到了两个 for 循环，所以时间复杂度为 O（n^2）。没有用到额外的空间，所以空间复杂度为 O（1）。
优化思考：也许通过减少第二个 for 嵌套，用数组来保存，就能减少不少时间复杂度，虽然用了额外空间。
完整代码：
import lombok.AllArgsConstructor;import lombok.Data;
import java.util.Objects;
public class MergedNodeFinder {
private static int mListLength; private static int nListLength; private static ListNode mListFirstNode; private static ListNode nListFirstNode;
public static void main(String[] args) { //初始化测试数据，没考虑空链表 initLists();
int minLength = Math.min(mListLength, nListLength); int maxLength = Math.max(mListLength, nListLength); ListNode mergedNode = null; ListNode mListCompareNode; ListNode nListCompareNode; int mListCompareIndex; int nListCompareIndex;
//从后往前取 for (int indexFromLast = 0; indexFromLast < minLength; indexFromLast++) { mListCompareIndex = mListLength - indexFromLast - 1; nListCompareIndex = nListLength - indexFromLast - 1; mListCompareNode = mListFirstNode; nListCompareNode = nListFirstNode;
//由于是单向链表，所以需要从头部开始遍历 for (int i = 1; i < maxLength - indexFromLast;i++) { if (i <= nListCompareIndex) { nListCompareNode = nListCompareNode.getNext(); } if (i <= mListCompareIndex) { mListCompareNode = mListCompareNode.getNext(); } }
//发现节点不相等，则停止查找。相等则继续往前查找 if (nListCompareNode.equals(mListCompareNode)) { mergedNode = nListCompareNode; } else { break; } }
//判断是否有交叉 System.out.println("是否有合并: " + Objects.nonNull(mergedNode) + " 合并的元素：" + mergedNode); }
private static void initLists() { /* //merge: null ListNode cNode = new ListNode('c', null); ListNode bNode = new ListNode('b', cNode); mListFirstNode = new ListNode('a', bNode); mListLength = 3;
ListNode fListNode = new ListNode('f', null); ListNode eListNode = new ListNode('e', fListNode); nListFirstNode = new ListNode('d', eListNode); nListLength = 3;*/
//merge: c ListNode cNode = new ListNode('c', null); ListNode bNode = new ListNode('b', cNode); mListFirstNode = new ListNode('a', bNode); mListLength = 3;
ListNode eListNode = new ListNode('e', cNode); nListFirstNode = new ListNode('d', eListNode); nListLength = 3;/* //merge: c ListNode dNode = new ListNode('d', null); ListNode cNode = new ListNode('c', dNode); ListNode bNode = new ListNode('b', cNode); mListFirstNode = new ListNode('a', bNode); mListLength = 4;
nListFirstNode = new ListNode('e', cNode); nListLength = 3;
//merge: a ListNode dNode = new ListNode('d', null); ListNode cNode = new ListNode('c', dNode); ListNode bNode = new ListNode('b', cNode); mListFirstNode = new ListNode('a', bNode); mListLength = 4;
ListNode eListNode = new ListNode('f', mListFirstNode); nListFirstNode = new ListNode('e', eListNode); nListLength = 6;
//merge: null mListFirstNode = new ListNode('a', null); mListLength = 1;
nListFirstNode = new ListNode('b', null); nListLength = 1;
*/ }
/* inner class */
@Data @AllArgsConstructor private static class ListNode {
private Object value;
private ListNode next;
}}复制代码
作业二：
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
没时间做，个人也不太清楚，有待学习
划线
评论
复制
发布于: 2020 年 07 月 27 日阅读数: 59
版权声明: 本文为 InfoQ 作者【iHai】的原创文章。
原文链接:【http://xie.infoq.cn/article/2300ffc909aaf54bd25cf8218】。文章转载请联系作者。
iHai
关注
还未添加个人签名 2018.07.26 加入
还未添加个人简介
评论