Oracle面试题

windy2335

昨天去oracle面试，阿三出了道面试题，
在此分享给各位，以集思广益：

写一个函数，判断两个链表是否相交，若相交，返回交点，不相交，返回NULL。

1. sNode * intersect(sNode *a,sNode *b)
   
2. {
   
3. ...
   
4. }

复制代码

要求：不许创建新的链表，尽量的少占内存，时间复杂度尽量小。


Ps:奶奶的，最悲剧的是，面试全程英文，阿三还有很浓的印度口音，听的太累。做出来后，还要用英文讲思路。擦。。。


有好方法的请下面跟帖...~

zylthinking

这个不就是一个两步一跳， 一个一步一跳的思路吗？
至于找到交点， 看http://bbs.chinaunix.net/redirec ... 81&ptid=3598431

ecjtubaowp

http://hi.baidu.com/baowup/blog/ ... cc42068701b025.html

windy2335

这个不就是一个两步一跳， 一个一步一跳的思路吗？
至于找到交点， 看
zylthinking 发表于 2011-11-29 11:02

    不错。~{:2_171:}

jonas_mao

关于链表的面试题有很多，可以去搜一下。
由于两个链表相交只能是Y型相交。所以一般的情况是判断最后的节点是否一样。但是还有一种情况是当一个链表的最后一个节点和另一个链表的任意节点相交时就不能只判断最后的节点了。

可以先算出两个链表的长度，然后以这个步长|L1 - L2| 来进行链表的比较：比如L2为短的，则L1链表以步长|L1 - L2|移动，L2以步长1移动。 判断两个链表的节点何时相等即可。