第八周作业

用户头像
changtai
关注
发布于: 2020 年 07 月 26 日
  • 有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



分析:

如果两个链表合并,那么从合并的节点开始,两个链表后面的所有的节点都是相同的。只要计算出两个链表长度的差abs(m-n),并且让长链表先移动abs(m-n),后面就可以同时遍历两个链表,并且比较节点是否相同,他们一定是同时到达合并节点的。

时间复杂度是:O(max[m,n])



代码如下:

public class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}



public class LinkedList<E> {
int size = 0;
/**
* Pointer to first node.
*/
Node<E> first;
/**
* Pointer to last node.
*/
Node<E> last;
public LinkedList(){
}
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
}



public class Test<E> {
public static void main(String[] args) {
Test<Character> test = new Test();
Character character_a = 'a';
Character character_b = 'b';
Character character_x = 'x';
Character character_y = 'y';
Character character_z = 'z';
Character character_d = 'd';
Character character_e = 'e';
Character character_f = 'f';
//第一个单向链表a->b->x->y->z
LinkedList<Character> linkedList1 = new LinkedList<Character>();
linkedList1.add(character_a);
linkedList1.add(character_b);
linkedList1.add(character_x);
linkedList1.add(character_y);
linkedList1.add(character_z);
//第二个单向链表d->e->f->x->y->z
LinkedList<Character> linkedList2 = new LinkedList<Character>();
linkedList2.add(character_d);
linkedList2.add(character_e);
linkedList2.add(character_f);
linkedList2.add(character_x);
linkedList2.add(character_y);
linkedList2.add(character_z);
test.findIntersection(linkedList1,linkedList2);
}
private void findIntersection(LinkedList<E> linkedList1, LinkedList<E> linkedList2){
//比较两个链表的元素的个数,多的放到longLinkedList,少的放到shortLinkedList
LinkedList<E> longLinkedList = null;
LinkedList<E> shortLinkedList = null;
if(linkedList1.size < linkedList2.size){
shortLinkedList = linkedList1;
longLinkedList = linkedList2;
}
//长链表先向后移动longLinkedList.size-shortLinkedList.size,拿到node
Node<E> node1 = longLinkedList.first;
Node<E> node2 = shortLinkedList.first;
E item = null;
for(int i=0; i<longLinkedList.size-shortLinkedList.size; i++){
node1 = node1.next;
}
//这个时候短链表与向后移动后的长链表是一样长的,同时进行遍历
for(int i=0; i<shortLinkedList.size; i++){
if(node1.item.equals(node2.item)){
item = node1.item;
break;
}
node1 = node1.next;
node2 = node2.next;
}
//如果有相交的元素,两个链表就是合并了
if(item != null){
System.out.println("两个链表合并了,合并的元素是:" + item);
}else{
System.out.println("两个链表没有合并");
}
}
}

执行结果:



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



用户头像

changtai

关注

还未添加个人签名 2018.04.30 加入

还未添加个人简介

评论

发布
暂无评论
第八周作业