假设链表均不带环
- 解法一： 判断第一个链表的每个结点是否在第二个链表中，时间复杂度为Ｏ(Length(A) * Length(B))。
- 解法二： 如果两个链表相交，就会有公共结点，而每个结点的地址唯一，因此可以根据是否存在地址一致的结点判断是否相交。对第一个链表的结点的地址进行hash排序，建立hash表，对第二个链表的结点的地址查询hash表，如果在hash表中存在，则相交。时间复杂度为Ｏ(Length(A) ＋ Length(B))。
- 解法三 反一个链表接在另一个链表的后面，如果得到的链表有环，说明两个链表相交。
- 解法四 因为每个结点只有一个next域，如果相交，它们最后一个结点肯定相同。把两个链表都遍历到最后一个结点，判断最后一个结点是否相同，相同就相交，否则，不相交。时间复杂度为Ｏ(Length(A) ＋ Length(B))。
扩展问题１
如果链表可能有环呢？上面的方法要怎么调整？
如果链表有环，可能在环内相交，也可能在环外相交。
- 还可以使用上面的解法三，只是在建立hash表的时候要有所不同，因为可能有环，需要判断是否遍历完成。可以用
set或map判断某个结点是否已经访问过了，如果已经访问过了，则停止遍历。然后遍历第二个链表，查看hash表中是否有结点的地址。 - 链表1 步长为1， 链表2步长为2 ，如果有环且相交则肯定相遇，否则不相交。
扩展问题２
如果我们需要求出两个链表相交的第一个节点呢？
对齐处理？？