数字之魅：判断两个链表是否相交

题目：给出两个链表的头指针，比如head1和head2，判断这两个链表是否相交。这里为了化简，我们假设两个链表均不带环。

方案一：蛮力法。一般我们都能想到的，就是从head1开始，逐个与head2中的每个结点的地址比较，看是否相等，如果不等，则head1移动到下一个结点，继续和head2中的每一个结点的地址比较;如果找到相等，则这两个链表相交;直到head1==null，则不相交。注意为了避免存在相同的元素，我们采取比较地址的方法，而不是比较元素，在判断链表里是否有环的时候，也是采用比较地址的方法。时间复杂度为o(n*n)。

方案二：利用空间换时间的做法。采用计数法。如果两个链表相交则说明该链表有相同的结点。而地址有时其唯一的标示，所以我们还是可以采取和方案一一样的比较地址的方案。只不过我们使用哈希表，将链表head1每个结点的地址进行hash取值，然后遍历haed2链表一遍，我们就可以得出是否有相同的结点，也就是是否存在相交。这里是时间复杂度为：o(n)=o(lenght(head1)+length(head2))+辅助空间o(lenght(head1))。

方案三：由于链表里没有环。那么我们可以将该问题进行转化，将head1头结点接到head2的尾部，这样我们就可以通过判断head2链表里有没有环来进行判断，他们是否相交。具体如下图所示。

如果head2没有环，则证明这两个链表不相交，如果head2里有环，则证明这两个链表相交。

具体如何判断链表是否有环。

方案四：由于只需要判断这两个链表时否相交，如果相交，那么这两个链表的最后一个结点一定是同一个，它们是‘y’字形的;但是如果不相交那就不存在这个特点。所以我们可以通过两次遍历，得到两个链表的最后一个结点，然后通过比较这两个链表的地址是否相同来判断它们是否相交。时间复杂度：o(lenght(head1)+length(head2))=o(n)。

 

 

这个题虽然比较简单，只是方案三里有一点儿值得学习的地方，就是我们可以将不熟悉的问题转化为我们熟悉的问题，这样在解决问题的时候就会简单很多。有些问题正面解决很难，但是通过转化以后就会很简单。