Microsoft : 找出相交两链表的交节点

两个单项链表彼此相交，求他们第一个交节点

回复 1# wwwyhx
相交之后的部分不是全都一样了吗？

回复 2# holyzz
感觉第一个方法更普适些，如果两个链表包含环的话第二个方法就不容易正常工作。不过都需要O(n)空间，不知道有没有像那个链表找环问题似的O(1)空间的解法

1.哈希一个链表的值，遍历另外一个链表看看有没有和节点在哈希表中，第一个这样的点就是第一个交点。
2.遍历2个链表得到两个链表的长度m和n。假设 M > N, 先从 长度为M的链表前遍历M-N个节点，然后 从长度为M的链表的M-N个节点，和 长度为N的链表的 节点 以相同的步进逐个比较，当发现两个节点的值想等时则为交点。
holyzz 发表于 2011-5-17 00:27

    恩，第二种方法是很好的解法

回复 5# wwwyhx
。。。还以为有什么别的方法，因为如果相交之后的部分存在环那就不方便求链表长度了。不过上面我也说错了，如果不考虑环，那这个做法应该只需要O(1)空间