架構師訓練營 week8 作業

关注

发布于: 2020 年 11 月 15 日

1. 有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
用環的概念來做，讓兩個鏈表各自往前，當到結尾的時候，就從另一個鏈表的頭開始。
此時會有兩種情況
在交叉點相會
在各自的結尾空節點相會
因為兩個指針所走的路一樣長，所以最後一定會相會
﻿
時間複雜度 O(m+n)
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end
# @param {ListNode} headA
# @param {ListNode} headB
# @return {ListNode}
def getIntersectionNode(headA, headB)
    return if headA.nil? || headB.nil?
    
    a = headA
    b = headB
    
    while a != b
        a = a.nil? ? headB : a.next
        b = b.nil? ? headA : b.next
    end
   
    a
end
﻿
2. DataNode节点宕机时HDFS处理过程的时序图﻿
﻿

发布于: 2020 年 11 月 15 日阅读数: 23

ilake

关注

还未添加个人签名 2019.04.15 加入

还未添加个人简介

发布

暂无评论