Question

如何判断单链表是否相交并找出第一交点

Answer 1

1.判断链表否是相交？
解法一：哈希表法，维护一个哈希表，分别遍历两个链表。将它们中的元素存入哈希表中，如果元素有重复那么两个链表就相交。

解法二：还有一种比较有想象力的解法，先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？
这样进行转换后就可以从链表头部进行判断了，其实并不用。通过简单的了解我们就很容易知道，如果新链表是有环的，那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的，从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。

解法三：仔细研究两个链表，如果他们相交的话，那么他们最后的一个节点一定是相同的，否则是不相交的。因此判断两个链表是否相交就很简单了，分别遍历到两个链表的尾部，然后判断他们是否相同，如果相同，则相交；否则不相交。

2.如果相交求出交点？
解法一：如果可以分配较多的内存，先遍历链表A，遍历链表A的时候将node加入到一个hash表或者二叉树中。之后遍历链表B的node时，检查该node是否存在在数据结构中对应的位置就可以了。可能会比原始方法快一些（如果交点在链表中靠后的位置，这个代价可能就比较大了，因为要维护多余的数据结构，因此这种情况下实践中效率很可能比原始方法慢），不过会使用较多的内存空间。

解法二：遍历两个表分别知道两个表的长度a, b。然后让长表先走|a-b|步后，短表再开始走，直到相同，则相同的的第一个节点为交点。