数仓的拉链表断链，交叉链，重复链的出现原因和解决方案？

2020-11-24 09:48发布

3条回答

2021-10-20 10:40

单链表相交指的是两个链表存在完全重合的部分，这两个链表相交于结点5，要求判断两个链表是否相交，如果相交，找出相交处的结点。

如果两个链表相交，那么它们一定会有公共的结点，由于结点的地址或引用可以作为结点的唯一标识，因此，可以通过判断两个链表中的结点是否有相同的地址或引用来判断链表是否相交。

具体可以采用如下方法实现：

首先遍历链表head1，把遍历到的所有结点的地址存放到HashSet中；

接着遍历链表head2，每遍历到一个结点，就判断这个结点的地址在HashSet中是否存在，如果存在，那么说明两个链表相交并且当前遍历到的结点就是它们的相交点，否则直到链表head2遍历结束，说明这两个单链表不相交。

算法性能分析

由于这种方法需要分别遍历两个链表，因此，算法的时间复杂度为O（n1+n2）。

其中，n1与n2分别为两个链表的长度。

此外，由于需要申请额外的存储空间来存储链表head1中结点的地址，因此，算法的空间复杂度为O（n1）。