架构师训练营第八周作业
发布于: 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, 下面的连接的代码更加优雅。
请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。
划线
评论
复制
发布于: 2020 年 07 月 24 日阅读数: 74
Melo
关注
还未添加个人签名 2019.09.17 加入
还未添加个人简介
评论