淘宝2012校招题目，高手们请进

geek2011

抽象为判断两个单链表是否相交，找交点的问题。
①判断一个单向链表是否有环，如果有环则找到环的入口节点。
②判断两个单向链表是否相交，如果相交则找到交点节点。
算法思想：①用两个指针p1,p2同时指向链表的头部，p1一次移动一步，p2一次移动两步，如果最终p1和p2重合则说明链表有环，如果p2走到空指针（链表的结尾）则说明链表无环。如果最终p1和p2重合，使p2重新指向链表的头结点，然后p1和p2同时一次移动一步，当p1和p2再次重合时该节点指针就是环的入口节点指针。
②有了第一问的算法基础，应该不难理解第二问。首先将其中一个链表list1首尾相接，变成一个有环链表，如果另一个链表list2和list1相交的话，list2也将成为一个有环链表，并且环的入口节点就是两个链表的交叉节点。如果两个链表不相交，则list2依然是一个无环链表。

空间复杂度O(1)，时间复杂度O(m)，m是其中一个节点的深度。

zylthinking

抽象为判断两个单链表是否相交，找交点的问题。
①判断一个单向链表是否有环，如果有环则找到环的入口节点 ...
geek2011 发表于 2011-09-26 17:54

想法不错， 不过似乎不符合实际： 树分支无数， 可不是一个简单 next 就能搞定的
即便可以， 这个方法能找到的不过是两个链表是否相交的结论， 相找交点， 除非将所有节点访问次数记录下来， 多次遍历后，找到第一个访问次数大于1的节点， 又是一个吃力不讨好的活

wingforce

想法不错， 不过似乎不符合实际： 树分支无数， 可不是一个简单 next 就能搞定的
即便可以， 这个方法 ...
zylthinking 发表于 2011-09-26 18:01

不需要，他的这个方法是对的，没任何人问题
无论多少岔路的树，从树叶向根走过去的路径就是链表，可以唯一确定

zylthinking

嗯我想错了，但第二个问题仍存在

zylthinking

我第二问题又想错了，确实是一个可行方法， 学到一招

weimeili1314

可以用LCA的Tarjan算法，这是一种离线算法，那个小狗撒尿是在线算法，要比那个快很多的。。。可以参考下。。。

snowboy9859

抽象为判断两个单链表是否相交，找交点的问题。
①判断一个单向链表是否有环，如果有环则找到环的入口节点 ...
geek2011 发表于 2011-09-26 17:54

    将二叉树转换成单链表，好主意。但我不明白为什么要判断这个单链表是否有环，二叉树转换的单链表会存在环么？

snowboy9859

我第二问题又想错了，确实是一个可行方法， 学到一招
zylthinking 发表于 2011-09-27 00:13

    抽象为判断两个单链表是否相交，找交点的问题。兄台 ，你这个问题理解清楚了么？能否告诉我为何要判断单链表是否有环？我可以理解为该问题是分别把两个当前结点和它所有的祖先结点组成一个单链表，再求该单链表的结点么？

snowboy9859

抽象为判断两个单链表是否相交，找交点的问题。
①判断一个单向链表是否有环，如果有环则找到环的入口节点 ...
geek2011 发表于 2011-09-26 17:54

    如果最终p1和p2重合，使p2重新指向链表的头结点，然后p1和p2同时一次移动一步，当p1和p2再次重合时该节点指针就是环的入口节点指针。
这个方法求交点实在是高，请问这样求交点是不是不能保证遍历一次就能把交点求出，可能需要N次遍历。（p1和p2同时一次移动一步，如果不能在环的入口节点处重合，那么它们永远都不可能重合）

A.com

1、判断下A节点的父节点有没有被标记，如果有，结束
2、标记该节点并上溯
3、判断下B节点的父节点有没有被标记，如果有，结束
4、标记该节点并上溯
5、循环上面四步