训练营第八周作业

关注

发布于: 2020 年 12 月 11 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode l1 = headA;
        ListNode l2 = headB;
        int n1 = 0;
        while (l1 != null) {
            n1++;
            l1 = l1.next;
        }
        int n2 = 0;
        while (l2 != null) {
            n2++;
            l2 = l2.next;
        }
        if (n1 > n2) {
            int c = n1 - n2;
            for (int i = 0; i < c; i++) {
                headA = headA.next;
            }
        } if (n2 > n1){
            int c = n2 - n1;
            for (int i = 0; i < c; i++) {
                headB = headB.next;
            }
        }
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
思路：算出两个链表的差值，然后让长链表先走差值这个步数，这样两个链表就同长了，然后再遍历比较就可以了。这样做，时间复杂度是O(m+n)
﻿
在Leecode 上找了另外一个解法：
﻿
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != l2) {
            l1 = l1 == null ? headB : l1.next;
            l2 = l2 == null ? headA : l2.next;
        }
        return l1;
    }
思路：双指针法。 假设两个链表的公共部分为 C. 那么 headA.size = A+C, headB.size = B+C. 让两个指针走 A+B+C的步数，他们必然会在第一个公共节点相遇。时间复杂度为O(m+n)
﻿
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
﻿