This topic has been archived. It cannot be replied.
-
工作学习 / 专业技术讨论 / 算法问题求教：有两个单向链表A和B，均不知其长度和是否闭合，请设计一个算法，验证两个链表是否相交（即是否存在An->next = Bm->next）。该问题是微软面试题，逐一比较复杂度为O{n*n}，显然不是他们要的答案
-xxjjs(东方射日);
2005-12-7
(#2650109@0)
-
1) 检查链表头 ;若next-node 相等,则相交, else 2);
2) 搜索到练表尾(or到头);检查链表尾,若两练表尾相同,则相交;
复杂度为O{n}
-eagle_no1(瞎起哄);
2005-12-7
(#2650201@0)
-
开环可以用您老的办法，检查链尾，但是如果是闭环呢？我一直没想出什么好办法。（闭环不一定从头开始，可以从任何一个地方开始闭环）
-xxjjs(东方射日);
2005-12-7
(#2650223@0)
-
把表头掐住,到了头就是尾.
-eagle_no1(瞎起哄);
2005-12-7
(#2650260@0)
-
a->b->c->d->e->c， 进了闭环，你就永远回不到头了
-xxjjs(东方射日);
2005-12-7
(#2650289@0)
-
我觉得这不是他们的本意。这不是通常意义的闭环链表。所有的通常链表算法对你的链表都不适用。
-holdon(again);
2005-12-7
(#2650341@0)
-
别低估鬼子们设计陷阱的能力，我估计如果你用了这个算法，下个问题就是问这种闭环的情况如何处理了。依据后来的对话，我还是觉得他们想问的是楼下所说的算法
-xxjjs(东方射日);
2005-12-7
(#2650436@0)
-
可以用改进的闭环测试的办法, 设两对指针, p1,p2指link1, p3,p4 指link2, p1、p3每次+1, p2、p4每次+2, 比较p1和p4、 p2和p3, 如相同则有交叉。当p1==p2 AND p3==p4时stop。算法应该是O(4*max(m,n))的。
-canadiantire(轮胎-M.I.N.K.);
2005-12-8
(#2651013@0)
-
不对，你这个比逐一比较还差。设10对指针也没用
-yuanzidan(原子弹);
2005-12-8
(#2651061@0)
-
请给出反例，不要泛泛的说“比逐一比较还差”。
-canadiantire(轮胎-M.I.N.K.);
2005-12-8
(#2651068@0)
-
这个算法是正确的，复杂度O(n)
-stevensun2000(小胖子);
2005-12-8
(#2651104@0)
-
这个算法是正确的，复杂度O(n*n)worst case必须等link1的所有值与link2的所有值都比较过一遍，才能得到结果。所以是n*n
-benlin(默默向上游);
2005-12-8
{81}
(#2651280@0)
-
it is not, man
-open(-close);
2005-12-8
(#2651295@0)
-
好像你是对的．能严格证明么？
-benlin(默默向上游);
2005-12-8
{895}
(#2651410@0)
-
OK
-canadiantire(轮胎-M.I.N.K.);
2005-12-8
{835}
(#2651494@0)
-
That's good. Thanks.
-benlin(默默向上游);
2005-12-8
(#2651602@0)
-
算法有个小问题:如果是奇数个NODE形成CLOSE LOOP, 有可能P2,P4回来的时候不等于P1,P2,稍微改进应该可以解决问题.但是,时间又要加多一点.
-iwantcar(EnjoyStudying);
2005-12-10
(#2655346@0)
-
oh. 也可能没有问题,在那里拼命转,两个指针估计是总有机会撞上的.
-iwantcar(EnjoyStudying);
2005-12-10
(#2655361@0)
-
哎，不用拼命转，赶上就能碰上，不会MISS的。。。
-yuanzidan(原子弹);
2005-12-10
(#2655375@0)
-
没有意识到是链表而不是TREE，而是考虑这种情况：
A-B-C-E-G-I-K
1-G-2-3-4-6
again my bad...:(
-yuanzidan(原子弹);
2005-12-8
(#2651219@0)
-
i believe this is correct answer, btw, O(4*max(m,n)) is still O(n)
-open(-close);
2005-12-8
(#2651118@0)
-
Thanks, I know that.
-canadiantire(轮胎-M.I.N.K.);
2005-12-8
(#2651123@0)
-
i know u know that, but someone may not :))))
-open(-close);
2005-12-8
(#2651130@0)
-
改进的闭环测试的办法, 设两对指针, p1,p2指link1, p1每次+1, p2每次+2, is standard answer for 闭环测试 and it is O(n)
-open(-close);
2005-12-8
(#2651121@0)
-
my bad...
-yuanzidan(原子弹);
2005-12-8
(#2651163@0)
-
SORRY.
-iwantcar(EnjoyStudying);
2005-12-9
(#2652745@0)
-
算法有错。假设A 为 P1, P2, ...Pn, Pn->next == P1,
B 为 Pa, Pb, Pc, Pc->Next== P5,
B的tail 是P4.
A 长度为n, B 长度为 m, 复杂度应该为 n+2m
1. compare P1...->Pn to Pa, ==,yes. or get A's P1 and Pn
2. Compare B's Pb,Pc ... to P1 and Pn , == yes.
-holdon(again);
2005-12-7
{251}
(#2650330@0)
-
不对，我的贴子好像也有错。
-holdon(again);
2005-12-7
(#2650350@0)
-
A p1,...pn, B pa,pb, pc->Next ==P5时，eagle的算法就出不来了。我的好像还可以。
-holdon(again);
2005-12-7
(#2650361@0)
-
2 应该是compare Pb,Pc to P1,Pn, Pa. px==null or Px==Pa就是不相交
-holdon(again);
2005-12-7
(#2650387@0)
-
哈希表1，把链表A放入哈希表，直到出现重复或者链表结束。重复就表示这个链表闭合。
哈希表的插入，应该是lg(n)吧？
2，把链表B放入同一个表，直到出现重复或者链表结束。重复的时候，查看哈希表原有的元素。如果这个元素是链表B的，说明链表B闭合。如果元素是链表A的，说明两表相交。
复杂度： nlgn
-benlin(默默向上游);
2005-12-7
{275}
(#2650242@0)
-
我想这应该是他们想要的答案了因为当我说我可以逐个比较，但是我想不是个好办法的时候，他们问我是否知道Big O，同时问我快速排序和冒泡排序的区别时，我说出两者复杂度是N*N和lgN，他们又问那如果排序后再查找呢，我说那会快些，复杂度是NlgN，但是空间复杂度提高了，他们就接入下一个问题.....
-xxjjs(东方射日);
2005-12-7
{246}
(#2650300@0)
-
一个抽象的算法，你怎么构造这个hash表？
-holdon(again);
2005-12-7
(#2650347@0)
-
面试中一般只要有一个idea就可以了，不需要详细的实现过程
-xxjjs(东方射日);
2005-12-7
(#2650439@0)
-
不用这么复杂吧？
-angelscallingme(Angel);
2005-12-8
{541}
(#2650906@0)
-
你这个方法简单是简单了，可不就是复杂度太高了些么？n*n显然比nlgn要大些吧？
-xxjjs(东方射日);
2005-12-8
(#2650919@0)
-
哈哈, 你这个跟楼上哈希很像呢! 他的哈希隐含着定义一个单影射函数, 计算时间可以忽略不记. 你的隐含着逐个比较, 比较时间是要计的. 如果你把比较的部份改进一下的话, 可能就变成他的哈希了.
-x888(我可不敢刷网了);
2005-12-8
(#2650925@0)
-
很多这种题都能归纳到这种模型，求一个SET A里的东西是否在另外一个SET B里。关键是把A放在某种DATA STRUCTURE C 里面(HASHTABLE，MAP，TREE。。。)。 再拿B里的每个对C搜索和比较。如果不对A/B进行处理，不关用什么算法，都逃不过O(N*N)
-yuanzidan(原子弹);
2005-12-8
{51}
(#2651076@0)
-
此言理论高度不错，有种俯瞰大局的意思。
-akoei(停车**枫林晚);
2005-12-8
(#2651416@0)
-
根据你的叙述 (加上假定所提供的链表指针不是随意，你并未说明这一点)，从拓扑结构上看，只能逐一比较，UNTIL发现至少一个链表发生循环或X->NEXT == NIL。此致
敬礼！
-maer(马儿);
2005-12-8
{12}
(#2651526@0)
-
o(2n)1. go to the end of link1. change the next field of every node to null when going. remember the address of last node in Var A. NEXT FIELD OF Last node is NULL for sure.
O(n)
2. from the start of link2 go, change the next field of every node to null when going. if you can find A. return true.
O(n)
3. return false WHEN SEE NEXT FIELD NULL
TOTAL O(2N)
change the next field of every node to null when going is the key to prevent close loop.
-iwantcar(EnjoyStudying);
2005-12-9
{460}
(#2652736@0)
-
BY THE WAY, IF YOU WANT TO KEEP THE OLD LIST. THIS WAY MAY NEED TO CONSTRUCT 2 NEW LIST TO REMEMBER ADDRESS OF THEM AT THE SAME TIME.
-iwantcar(EnjoyStudying);
2005-12-9
(#2652765@0)
-
haha, And my way has less if statement than yours.
-iwantcar(EnjoyStudying);
2005-12-9
(#2652776@0)
-
You won't see A in step (2), because you have set next field of all link1's node to NULL in step (1).
-canadiantire(轮胎-M.I.N.K.);
2005-12-9
(#2652926@0)
-
Exactly!
-benlin(默默向上游);
2005-12-9
(#2653001@0)
-
You are right.
Let me change it in this way:
-iwantcar(EnjoyStudying);
2005-12-9
{657}
(#2653073@0)
-
you are not supposed to change the node structure. What you did actually fall into this model(#2651076). You would never know whether this node has been visited or not without doing search/compare
-yuanzidan(原子弹);
2005-12-9
(#2653108@0)
-
where is this contraints from? If you add this constraints, I can add others to make any agorithm wrong.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653289@0)
-
no offence. Whole date structure copy is extremely time and space consuming. That should be avoided if it's possible. Remember, list length may be huge as well as the node size.The time complexity of copying a huge node will be another story. You are just wasting your time trying to get minor time complexity improvement but with major space complexity cost and potential more time complexity cost .
-yuanzidan(原子弹);
2005-12-9
{224}
(#2653351@0)
-
How do you think I will copy the whole structure? I just copy the address.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653356@0)
-
when you change the next, if you dont copy, how can you restore the list?
-yuanzidan(原子弹);
2005-12-9
(#2653361@0)
-
addresses will help you restore.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653368@0)
-
#2653141 read it and think hard. you may understand more.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653369@0)
-
Think about it. restoring is not that easy. how do you retore? how do you know which is which?
-yuanzidan(原子弹);
2005-12-9
(#2653379@0)
-
If you are really want to make this topic huge: 1. Use vitual page system to store the adresses. 2. From the addresses to restore a link is very easy, think. Or read data structure books if you happen to forget.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653399@0)
-
Sorry, out for lunch. From the addresses to restore a link is not that easy without creating a new structure and it's system/language dependent. see #2653593
-yuanzidan(原子弹);
2005-12-9
(#2653610@0)
-
I store it in the Virtual page system. If you don't know it, read operating system books.
Or read Win32 / Base service SDK. Otherwise, you can malloc blocks of memory to do that. A little bit more difficult.It is not always necessary to store things in a linked list.
-iwantcar(EnjoyStudying);
2005-12-9
{60}
(#2654002@0)
-
Knowing several tech words means nothing. I know more than you when I was in school, and my ms thesis happened to be OS related. YOU are not using "Virtual page system",your OS uses that and you MAY have a OS without it. Algorithm should not depend on system/language. When you talk about Algorithm later, please don't mention any system characters any more. you still dont answer #2653593, whereI asked where, I mean where in your Algorithms.
-yuanzidan(原子弹);
2005-12-9
{275}
(#2654083@0)
-
Ok. some system don't support linked list at all. And malloc can creat effective table for addresses. Faint! If you can't, doesn't means others can't.
-iwantcar(EnjoyStudying);
2005-12-9
(#2654215@0)
-
Bingo! You got the point! Those data structures like lists are system/language
interdependent. Without being implemented in some system/language does not prevent it to be used in Algorithm.You need improve your Algorithm concept. Again, don't mention malloc when you talk Algorithm, since someone may use some language which does not support dynamically allocating memory.
-yuanzidan(原子弹);
2005-12-9
{184}
(#2654317@0)
-
READ THIS AGAIN AND AGAIN: #2652765
-iwantcar(EnjoyStudying);
2005-12-9
(#2654609@0)
-
most of data structure is not completely system / language independent. And data structure is just a tool. I am able to implement my way in most popular luanguages. If you can't, your problem, not mine.Ok. I won't discuss this with you any more. I don't need you understand me at all.
-iwantcar(EnjoyStudying);
2005-12-9
{84}
(#2654674@0)
-
OK, let me rephrase this for you.1. Follow link1, compare next with MyNull and Null, If MyNull, stop, if it's Null, set to MyNull and stop, otherwise, set to MyNull,
2. follow link2, compare next with null and MyNull, if is Null, stop and return false, if it's MyNull, stop and return true.
3. restore link1
step1. O(m), 2 compares each step.
step2. O(n), 2 compares each
step3. O(m),
total O(3m + 2n) = O(n)
plus, memory comsumptions.
-canadiantire(轮胎-M.I.N.K.);
2005-12-9
{424}
(#2653141@0)
-
WHERE IS THE #DEFINE PART. seems YOU HAVE A LOT OF TIME.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653282@0)
-
Then yours? How many compare will your way takes?
-iwantcar(EnjoyStudying);
2005-12-9
(#2653297@0)
-
NO MEMORY CONSTRAINTS VERSION.NODE * MYNULL1;
NODE * MYNULL2;
MYNULL1 = &MYNULL1;
MYNULL2 =&MYNULL2 ;
//BECAUSE MYNULL2 AND MYNULL1 IS IN THE STACK, THOSE ADDESS WILL NOT BE ALLOCATED AGAIN. IT IS SAFE TO USE IT AS NULL.
-iwantcar(EnjoyStudying);
2005-12-9
{196}
(#2653391@0)
-
Then how do you tell it is kind of "NULL" instead of a next pointer?
-canadiantire(轮胎-M.I.N.K.);
2005-12-9
(#2653401@0)
-
here.
-iwantcar(EnjoyStudying);
2005-12-9
{695}
(#2653438@0)
-
WHERE do you store your old address here for later restore? and your have reserved room/fields in Node? Creating a new data type/structure is not worth and system/language dependent.
-yuanzidan(原子弹);
2005-12-9
(#2653593@0)
-
It is impossible for MYNULL equal to a next pointer. Because the value of MYNULL is equal to the addess of itself which is in the stack. MYNULL is a new variable.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653445@0)
-
That is exactly my point, MyNULL is a pointer, an address, when you traverse the linked-list, how can you tell it's a "NULL", not a pointer to next node?
-canadiantire(轮胎-M.I.N.K.);
2005-12-9
(#2653467@0)
-
I use MYNULL as constant. Just want it to be unique.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653499@0)
-
Please don't ask question in half a hour. I believe you can understand the entire thing. It took me 10 minutes to understand yours too.
-iwantcar(EnjoyStudying);
2005-12-9
(#2653506@0)