架构师训练营第八周作业
发布于: 2020 年 07 月 28 日
以下两题,至少完成一道
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。
1.链表
1.1方法一 两层链表遍历
先遍历链表1,内层嵌套遍历链表2,判断链表1的值和链表2节点的值是否相等
时间复杂度O(m*n)
空间复杂度
/*** 通过循环方式判断链表是否合并,时间复杂度O(m*n)* @param headA* @param headB* @return*/Boolean mergerOrNotByLoop(LinkedNode headA, LinkedNode headB) {LinkedNode currA = headA.next;while (currA != null) {LinkedNode currB = headB.next;while (currB != null) {if (currA.value.equals(currB.value)) {// System.out.println(String.format("链表A和链表B合并,A : %s , B : %s", currA.value, currB.value));return true;}currB = currB.next;}currA = currA.next;}return false;}
1.2方法二 放入栈中,判断栈顶元素是否相等
把链表1和链表2的元素分别压入栈中,判断栈顶的元素是否相等
时间复杂度O(m+n)
空间复杂度
/*** 把链表放入到栈中,判断栈顶元素是否相等 来判断链表是否合并* 时间复杂度O(m+n)* @param headA* @param headB* @return*/Boolean mergerOrNotByStack(@NotNull LinkedNode headA, @NotNull LinkedNode headB) {LinkedNode currA = headA.next;LinkedNode currB = headB.next;Stack<Object> stackA = new Stack<>();Stack<Object> stackB = new Stack<>();while (currA != null) {stackA.push(currA.value);currA = currA.next;}while (currB != null) {stackB.push(currB.value);currB = currB.next;}return stackA.isEmpty() || stackB.isEmpty() ? false :stackA.pop().equals(stackB.pop());}
1.3 完整代码如下:
import org.jetbrains.annotations.NotNull;import java.util.Stack;public class LinkedNode {public LinkedNode next;public Object value;public LinkedNode(Object value, LinkedNode next) {this.next = next;this.value = value;}public static void main(String[] args) {//构建链表AString[] arrayA = new String[]{"a", "b", "x", "y", "z"};//构建链表BString[] arrayB = new String[]{"d", "e", "f", "x", "y", "z"};LinkedNode headA = initLinkedList(arrayA);printLinkedList(headA);LinkedNode headB = initLinkedList(arrayB);printLinkedList(headB);if(mergerOrNotByLoop(headA, headB)){System.out.println("链表A和链表B合并");}else {System.out.println("链表A和链表B未合并");}if(mergerOrNotByStack(headA, headB)){System.out.println("链表A和链表B合并");}else {System.out.println("链表A和链表B未合并");}}/*** 初始化链表* @param values* @return*/static LinkedNode initLinkedList(@NotNull String[] values) {LinkedNode head = new LinkedNode(null, null);LinkedNode curr = head;for (String val : values) {LinkedNode node = new LinkedNode(val, null);curr.next = node;curr = node;}return head;}/*** 打印链表* @param head*/static void printLinkedList(@NotNull LinkedNode head) {LinkedNode curr = head.next;while (curr != null) {System.out.print(curr.value + " ");curr = curr.next;}System.out.println();}/*** 通过循环方式判断链表是否合并,时间复杂度O(m*n)* @param headA* @param headB* @return*/static Boolean mergerOrNotByLoop(LinkedNode headA, LinkedNode headB) {LinkedNode currA = headA.next;while (currA != null) {LinkedNode currB = headB.next;while (currB != null) {if (currA.value.equals(currB.value)) {// System.out.println(String.format("链表A和链表B合并,A : %s , B : %s", currA.value, currB.value));return true;}currB = currB.next;}currA = currA.next;}return false;}/*** 把链表放入到栈中,判断栈顶元素是否相等 来判断链表是否合并* 时间复杂度O(m+n)* @param headA* @param headB* @return*/static Boolean mergerOrNotByStack(@NotNull LinkedNode headA, @NotNull LinkedNode headB) {LinkedNode currA = headA.next;LinkedNode currB = headB.next;Stack<Object> stackA = new Stack<>();Stack<Object> stackB = new Stack<>();while (currA != null) {stackA.push(currA.value);currA = currA.next;}while (currB != null) {stackB.push(currB.value);currB = currB.next;}return stackA.isEmpty() || stackB.isEmpty() ? false :stackA.pop().equals(stackB.pop());}}
划线
评论
复制
发布于: 2020 年 07 月 28 日阅读数: 48
版权声明: 本文为 InfoQ 作者【涛】的原创文章。
原文链接:【http://xie.infoq.cn/article/59e395cb24496290857bd3302】。文章转载请联系作者。
涛
关注
还未添加个人签名 2018.04.25 加入
还未添加个人简介
评论