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

zylthinking

抽象为判断两个单链表是否相交，找交点的问题。兄台 ，你这个问题理解清楚了么？能否告诉我为何要 ...
snowboy9859 发表于 2011-10-05 11:01

求 A,B共同祖先， 设根节点 root, 则将 root->parant = A; 则组成环; 在B看来共同祖先为环入口， 问题转化为求环入口。
至于循环次数， 需要2遍即可， 这是一个很直白的数学问题， 仔细想想就能明白
自然也不是像帖子所说， 无条件开始第二遍， 而是在开始前先判断一把第一遍重合时步进为1的与步进为2的各走了几步， 如果步数不同， 则做些调整再开始步进均为1的第二次

snowboy9859

求 A,B共同祖先， 设根节点 root, 则将 root->parant = A; 则组成环; 在B看来共同祖先为环入口， 问题 ...
zylthinking 发表于 2011-10-05 17:39

    root->parant = A; 则组成环,在B看来共同祖先为环入口?这一点我不明白，a链表为循环链表，整个链表为一个环，在b看来，b链表应该是桥接在a链表中；请指教

snowboy9859

回复 82# zylthinking


    我理解了为什么共同祖先在环的入口，之前误解了，不好意思。a环改为循环链表类似于0，b环类似于日型的链表。thanks

btdm123

很简单，两边往上走呗

snowboy9859

回复 85# btdm123


    请授我以鱼

btdm123

回复  btdm123


    请授我以鱼
snowboy9859 发表于 2011-10-08 09:59

信口胡说而已，抱歉。其实出这种题目是典型的应试教育模式，我很反感，它是在规定你要怎么想，善解这种题目只是做题高手，没有发散思维。
真正有意义的题目应该把问题的完整的描述出来，这是个什么场景，为什么要用树，用的是什么树，为什么要找祖先节点，我能换一种数据结构来实现吗？
这些问题，都是实践中必然遇上的，出题者不让你去考虑，这就是应试教育的缺陷。