写点什么

架构师训练营第八周课后作业

用户头像
万有引力
关注
发布于: 2021 年 01 月 16 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。 请用代码(或伪代码)描述算法,并给出时间复杂度。

思路

此问题的关键在于找到判断是否合并的条件,即两个链表中是否存在指针相同的节点,如果存在这样的节点,即证明有合并出现,根据单链表的性质,后面的元素无需再遍历;

两个单链表分别为 A 和 B,首先遍历链表 A,将链表中的元素依次放入一个集合中;

然后遍历链表 B,逐一检查节点的引用是否已存在于 set 中,如果存在则直接返回这个节点,中止循环;

若所有的节点在 set 中不存在,则说明两个链表无合并。

核心代码

public static LinkedListNode findMergePoint(LinkedListNode aHead, LinkedListNode bHead) {    Set<LinkedListNode> nodeSet = new HashSet<>();    LinkedListNode mergePoint = null;    while(aHead != null) {      nodeSet.add(aHead);      aHead = aHead.next();    }    while(bHead != null) {      if(nodeSet.contains(bHead)) {        mergePoint = bHead;        break;      }      bHead = bHead.next();    }    return mergePoint;  }
复制代码

在线运行:

https://repl.it/@attrany/NativeSkeletalModule#Main.java

复杂度分析

此方法需要至少一次遍历链表 A,部分遍历链表 B,时间复杂度为 O(m+n)

因使用了 Set 对链表 A 中的元素进行了存储,因此空间复杂度为 O(m)

发布于: 2021 年 01 月 16 日阅读数: 16
用户头像

万有引力

关注

还未添加个人签名 2018.05.30 加入

还未添加个人简介

评论

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