求链表的第一个公共节点问题（好未来笔试题）

问题描述：给定两个链表的头指针，判断两个链表是否存在公共节点，如果存在公共节点，则找出第一个公共节点。

分析：这曾经是我参加好未来的一道笔试题目，给大家分享下解法。

        解法一：蛮力法。拿第一个链表的每个节点去和第二个链表的每个节点进行比较，如果都不相同，则判断出两个链表不相交。

                    否则输出第一个相同的节点。算法的时间复杂度为O(m*n).

        解法二：辅助空间法。仔细观察可以发现，如果两个链表想要相交，则尾节点必是相交点，否则不相交。

                    因此我们可以从两个链表的尾部开始进行比较，如果不相同，直接判断出不相交。

                   如果相同，记下这个节点，然后继续往前比较，如果仍然相同，记下这个节点，如此进行下去，直到碰到不同的节点为止，

                   那上次保存的节点就是第一个相交的节点。但是由于单链表只能从头开始遍历，不能从尾部向头遍历，需要采用一些办法来实现，

                   这个属于典型的先进后出，因此可以使用栈来实现，需要利用两个辅助栈实现，首先将两个链表中的所有节点入栈，然后再从栈顶开始                    比较。

                   算法的时间复杂度为O(m+n).

        解法三:  由于解法二需要额外的辅助空间，可以再加以改进。

                   可以先将两个链表扫描一遍求出各自的长度为m和n，并假设m>=n，这样，可以先在长的链表上遍历m-n个节点，然后再在两个链表                    上同时开始遍历， 并比较节点是否相同，如碰到第一相同的节点，就可以结束了，如果遍历完都没有相同的节点，那么就可以判断                        出，两个链表没有交点。

                   算法的时间复杂度为O(m).

 

由于比较简单，我就不再些具体的代码了，读者可以自行验证。