请教一道面试题

anselcat

有两个单链表A，B  节点的值是无序的，在链表A中的一个节点的值和链表B中的一个节点的值是相等的，求出这个值。我回答用hash做，结果面试管不满意，请问还有什么好方法啊

5毛党党员

不是直接遍历吗？

雨过白鹭洲

串连、排序、遍历

alexhappy

先排序，再查找。。。。

cloudice

3L想法不错

typ_adam

串连的想法很好

lemoncookie

这个法子不比hash强阿

cloudice

hash在比较长链的时候实现起来不太容易吧~

w_anthony

假设A链表有m个元素，B链表有n个元素。
如果是最傻的直接遍历，那算法复杂度是O(m*n)。
先不管是什么算法，由于无序性，最快的应该是O(m+n)。
不过无论如何，似乎都需要用到排序，那么算法复杂度应该是O((m+n)*排序)
对于这种未知类型，似乎线性排序似乎用不了，排一次序估计也只是对数阶的。
目前只想到用std::set的二叉树做一个堆排序，方法就是交替着把两个链表的元素往set里面扔，哪次返回失败，那这个元素就是重复的。
算法复杂度在O(m+n)到O((m+n)(1+log2+log3+……+log(m+n))之间，比较靠RP。

alexhappy

可以这样做：
将listA接点中的值依次减去一个数num（num可任意，比如可以选择为表首接点的值，但不要是0），将结果放在一个数组array中
将listB接点中的值依次减去那个数num，将结果与array中的元素进行比队，找到就OK了