架构师训练营 -week08

关注

发布于: 2020 年 11 月 15 日

1、有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
解题思路：
合并两个单链表，由于没有说是有序，所以可以在任何地方合并，另外合并意味着在合并点后续所有的节点的数据是一样的。
1、首先计算两个链表的长度以及链表的尾节点，如果最后节点不相同，则肯定不能合并。
2、找出两个链表中的长链表，如果两个链表能合并且长度不同，那么短链表为长链表的子集。
3、循环比较两个链表的头结点，如果相同则返回该结点，不同则继续向后移动指针。
具体代码如下：
    public ListNode combine(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return null;
        }
        // 首先算出两个链表的长度以及最后链表的节点，如果最后节点不相同，则肯定不能合并
        int lenA = 1, lenB = 1;
        ListNode tempA = a;
        ListNode tempB = b;
        while (tempA.next != null) {
            lenA++;
            tempA = tempA.next;
        }
        while (tempB.next != null) {
            lenB++;
            tempB = tempB.next;
        }
        if (tempA._value != tempB._value) {
            return null;
        }
        // 两个链表合并，如果长度不同，那么短链表为长链表的子集，否则需要排除掉前面不等的节点
        int len = Math.abs(lenA - lenB);
        if (lenA > lenB) {
            tempA = a;
            tempB = b;
        } else {
            tempA = b;
            tempB = a;
        }
        for (int i = 0; i < len; i++) {
            tempA = tempA.next;
        }
        // 尾结点已经相等，现在判断头结点
        while (tempA._value != tempA._value) {
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return tempA;
    }
    static class ListNode {
        int _value;
        ListNode next;
        public ListNode(int value, ListNode next) {
            this._value = value;
            this.next = next;
        }
    }
2、请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
﻿