链表相交问题

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

解答：首先了解一下这个问题的工程实践，例如在一个大的系统中，如果出现两个
链表相交的情况，一旦程序释放了其中的一个链表的所有节点，那样就会造成第二
个链表信息的丢失。因此，我们需要在释放一个链表之前知道是否有其他链表与当
前链表相交。


方法一：判断两个链表的尾指针是否相等。
先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时
和第一个链表的最后节点做比较，如果相同则相交，不同则不相交。
这样的时间复杂度为O(length(h1)+length(h2))，而且只用一个额外的指针来存储
最后一个节点的指针。

方法二：将问题转化为链表是否有环。

由于两个链表都不带环，所以我们可以把第二个链表接在第一个链表的后面，如果得到的链表
有环，则说明这两个链表相交，否则，说明两个链表不相交。
-------------------------------------------------------------------------------------------------------------------

问题拓展：
如果两个链表相交，如何求两个链表的第一交点。

顺序遍历两个链表到尾节点时，我们并不能保证在两个链表上同时到达尾节点。
这是因为两个链表长度不一定一样。如果假设链表1比链表2多x个节点，我们
可以先在链表1上遍历前x个节点，之后再和链表2同步遍历，这样就可以保证
同时到达最后一个节点了。由于两个链表从第一个公共节点开始到链表的尾节
点部分都是重合的，因此，它们肯定也同时到达第一个公共节点。在遍历中，
第一个相同的节点就是第一个公共的节点。

最后我们的方案是：先分别遍历两个链表得到它们的长度，并求出两个长度之差x。

在长链表上先遍历x次之后，再同步变量第二个链表，直到找到相同的节点或一直

到链表结束。

该算法的时间复杂度是O(Length(head1)+Length(head2))。