写点什么

训练营第八周作业

用户头像
大脸猫
关注
发布于: 2020 年 12 月 11 日
  1. 有两个单向链表(链表长度分别为 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)



  1. 请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。



用户头像

大脸猫

关注

还未添加个人签名 2018.04.27 加入

还未添加个人简介

评论

发布
暂无评论
训练营第八周作业