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

有两个单向链表（链表长度分别为 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)