第 8 周作业
发布于: 2020 年 12 月 13 日
一、作业说明
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
二、作业实现
package online.chenkai.loan.market.example;
import java.io.Serializable;import java.util.Objects;
/** * 链表相交判定、相交点检索 * * @author chenkai 2020-12-13 22:21:00 * @version 1.0.0 */public class NodeExample {
/** * 单向链表 */ public static class Node implements Serializable {
private static final long serialVersionUID = -4105988897516484129L; /** * 数值 */ int data;
/** * 下1节点 */ private Node next;
public Node getNext() { return next; }
public void setNext(Node next) { this.next = next; }
@Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof Node)) { return false; } Node node = (Node)o; return data == node.data && Objects.equals(getNext(), node.getNext()); }
@Override public int hashCode() {
return Objects.hash(data, getNext()); } }
/** * 链表相交判定、相交点检索 * * @param head1 链表1头 * @param head2 链表2头 * * @return Node 相交点;null=不相交 */ private Node find(Node head1, Node head2) { if (Objects.isNull(head1) || Objects.isNull(head2)) { return null; }
// 链表长度 int length1 = 0; int length2 = 0; Node cursorNode1 = head1; Node cursorNode2 = head2; while (Objects.nonNull(cursorNode1.next)) { cursorNode1 = cursorNode1.next; length1++; } while (Objects.nonNull(cursorNode2.next)) { cursorNode2 = cursorNode2.next; length2++; } // 单向链表尾部相同则存在相交,反之不存在相交 if (!Objects.equals(cursorNode1.getNext(), cursorNode2.next)) { return null; } int diff = Math.abs(length1 - length2);
/* ************************ 寻找相交节点 ************************* */ // 重置指针 if (length1 > length2) { cursorNode1 = head1; cursorNode2 = head2; } else { cursorNode1 = head2; cursorNode2 = head1; } // 较长链表指针后移 for (int i = 0; i < diff; i++) { cursorNode1 = cursorNode1.getNext(); } // 相交点查询 while (!Objects.equals(cursorNode1, cursorNode2)) { cursorNode1 = cursorNode1.getNext(); cursorNode2 = cursorNode2.getNext(); } return cursorNode1; }}
复制代码
实现逻辑
判定链表尾部相交，首先判定是否相同,如相同存在相交,反之不相交
如存在相交，较长链表移动指针保持与较短链表相同长度，较少遍历次数
时间复杂度 O(m+n)
划线
评论
复制
发布于: 2020 年 12 月 13 日阅读数: 32
Rocky·Chen
关注
还未添加个人签名 2018.03.03 加入
还未添加个人简介
评论