架构师训练营第 8 周课后练习

关注

发布于: 2020 年 12 月 13 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用代码（或伪代码）描述算法，并给出时间复杂度。
时间复杂度：O(m+n)，最多循环m+n次。
空间复杂度：O(1)
    public class Node<T>
    {
        public T Data { get; set; }
        public Node<T> Next { get; set; }
        public Node(T data)
        {
            this.Data = data;
            this.Next = null;
        }
    }
    
    public class List<T>
    {
        public Node<T> Head { get; private set; }
        public void InsertLast(Node<T> node)
        {
            if (this.Head == null)
            {
                this.Head = node;
                return;
            }
            var current = this.Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = node;
        }
        public void InsertLast(T data)
        {
            InsertLast(new Node<T>(data));
        }
    }
    
    public class Program
    {
        public static void Main(string[] args)
        {
            var common = new List<string>();
            common.InsertLast("x");
            common.InsertLast("y");
            common.InsertLast("z");
            var list1 = new List<string>();
            list1.InsertLast("a");
            list1.InsertLast("b");
            list1.InsertLast(common.Head);
            var list2 = new List<string>();
            list2.InsertLast("d");
            list2.InsertLast("e");
            list2.InsertLast("f");
            list2.InsertLast(common.Head);
            var node = FindCommonNode(list1, list2);
            Console.WriteLine($"Common Node is { node?.Data }");
        }
        public static Node<T> FindCommonNode<T>(List<T> list1, List<T> list2)
        {
            if (list1 == null || list2 == null)
                return null;
            var head1 = list1.Head;
            var head2 = list2.Head;
            var p1 = list1.Head;
            var p2 = list2.Head;
            while (p1 != p2)
            {
                p1 = p1 == null ? head2 : p1.Next;
                p2 = p2 == null ? head1 : p2.Next;
            }
            return p1;
        }
    }
﻿
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
﻿