写点什么

架构师训练营第八周作业

用户头像
Melo
关注
发布于: 2020 年 07 月 24 日

作业1: 判断两个链表是否能合并?

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



O(N)的时间复杂度。

先跳过较长的链表中多出来的节点,比如链表1长度为5,链表2长度为3。那么链表1就要从开头跳两个节点到第三个。然后直接遍历两个链表,找出共同的尾巴。逻辑较为简单,就直接用Java写了。



// 简易的单链表

SinglyLinkedList.java

public class SinglyLinkedList<T> {
Node<T> head;
Node<T> tail;
int size;
public SinglyLinkedList(Node<T> head) {
this.head = head;
this.tail = head;
size = 1;
}
public void add(Node<T> node) {
tail.next = node;
tail = node;
++size;
}
}



// 简易的单链表节点

Node.java

public class Node<T> {
public Node<T> next = null;
public T value;

public Node(T value) {
this.value = value;
}
}




//CommonTails.java

import java.util.Arrays;
import java.util.List;
public class CommonTails<T> {
public Node<T> findCommonTails(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2) {
// Edge case consideration
if (list1.size == 0 || list2.size == 0) {
return null;
}
// Find the first positions for both lists where a common tail can be found.
// O(n)
List<Node<T>> candidates = findCandidates(list1, list2);
// Find the common tails from candidates
// O(n)
return getCommonTailsFromCandidates(candidates, Math.min(list1.size, list2.size));
}
private Node<T> getCommonTailsFromCandidates(List<Node<T>> candidates, int size) {
Node<T> common = null;
Node<T> node1 = candidates.get(0);
Node<T> node2 = candidates.get(1);
System.out.println(node1.value);
System.out.println(node2.value);
System.out.println(size);
for (int i = 0; i < size; i++) {
if (node1.value.equals(node2.value)) {
if (common == null) {
common = node1;
}
} else {
if (common != null) {
common = null;
}
}
node1 = node1.next;
node2 = node2.next;
}
return common;
}
private List<Node<T>> findCandidates(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2) {
int length1 = list1.size;
int length2 = list2.size;
int diff = Math.abs(length1 - length2);
if (length1 == length2) {
return Arrays.asList(list1.head, list2.head);
}
if (length1 > length2) {
Node<T> node = advance(diff, list1);
return Arrays.asList(node, list2.head);
} else {
Node<T> node = advance(diff, list2);
return Arrays.asList(node, list1.head);
}
}
private Node<T> advance(int diff, SinglyLinkedList<T> list) {
Node<T> cur = list.head;
while (diff > 0) {
cur = cur.next;
--diff;
}
return cur;
}
}



Test.java

public class Test {
public static void main(String[] args) {
CommonTails<Character> finder = new CommonTails<>();
Node<Character> node1 = new Node<>('a');
SinglyLinkedList<Character> list1 = new SinglyLinkedList<>(node1);
Node<Character> node2 = new Node<>('b');
Node<Character> node3 = new Node<>('c');
Node<Character> node4 = new Node<>('d');
Node<Character> node5 = new Node<>('e');
list1.add(node2);
list1.add(node3);
list1.add(node4);
list1.add(node5);
Node<Character> node6 = new Node<>('b');
SinglyLinkedList<Character> list2 = new SinglyLinkedList<>(node6);
Node<Character> node7 = new Node<>('k');
Node<Character> node8 = new Node<>('v');
Node<Character> node9 = new Node<>('e');
list2.add(node7);
list2.add(node8);
list2.add(node9);
Node<Character> commonNode = finder.findCommonTails(list1, list2);
if (commonNode == null) {
System.out.println("No common tails");
} else {
System.out.println("Common tails Found. The value is " + String.valueOf(commonNode.value));
}
}
}



后来参考了一下Leetcode 160, 下面的连接的代码更加优雅。

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!



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





用户头像

Melo

关注

还未添加个人签名 2019.09.17 加入

还未添加个人简介

评论

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