1.算法题
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
以下实现的时间复杂度是 O(m+n+Max(m,n))
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) {return null;} int lenA = 0; int lenB = 0; ListNode aNode = headA; ListNode bNode = headB; while(aNode != null){ lenA++; aNode = aNode.next; } while(bNode != null){ lenB++; bNode = bNode.next; } aNode = headA; bNode = headB; if (lenA >= lenB) { for(int i = lenA - lenB; i > 0; i--) { aNode = aNode.next; } } else { for(int i = lenB - lenA; i > 0; i--) { bNode = bNode.next; } } while (aNode != bNode) { aNode = aNode.next; bNode = bNode.next; } return aNode; }}
复制代码
2.请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
评论