好像你是对的．能严格证明么？ -benlin(默默向上游) @佛州华人论坛:佛州枫下论坛 The Rolia Forum of Florida

工作学习 / 专业技术讨论 / 算法问题求教：有两个单向链表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) -benlin(默默向上游); 2005-12-8 {81} (#2651280@0)
worst case必须等link1的所有值与link2的所有值都比较过一遍，才能得到结果。所以是n*n

it is not, man -open(-close); 2005-12-8 (#2651295@0)

好像你是对的．能严格证明么？ -benlin(默默向上游); 2005-12-8 {895} (#2651410@0)
我哈希表的解法肯定是nlgn，而且正确性肯定没问题。CT的解法复杂度比我的好，O(n)，只是怎么证明正确性？当

我的解法能用来证明Element A==Element B，而CT的解法使用了一个特性：只要两个链表相交，相交之后的元素就一定一样了。所以原子弹给出的例子

A-B-C-E-G-I-K 1-G-2-3-4-6
是不符合题意的。当link2上面有G的时候，下一个元素只能是I，然后K:
A-B-C-E-G-I-K 1-G-I-K
所以只要检查链尾相同就可以了（对没有闭环的情况）

对于有闭环的情况，如果二者相交，它们肯定在同一个闭环中间。（这时我前面没有想到的）。怎么证明 p1、p3每次+1, p2、p4每次+2, 比较p1和p4、 p2和p3, 如相同则有交叉。当p1==p2 AND p3==p4时stop，为什么这时候能肯定他们不相交？

补充一下这个解法：
设两对指针, p1,p2指link1, p3,p4 指link2, p1、p3每次+1, p2、p4每次+2, 比较p1和p4、 p2和p3, 如相同则有交叉。当p1==p2 AND p3==p4时stop。当p1,p2,p3,p4 ->next为空（即到达链尾）时保留原（链尾）值，这样就可以在最后比较链尾了。
现在请证明这个算法的正确性。

OK -canadiantire(轮胎-M.I.N.K.); 2005-12-8 {835} (#2651494@0)
首先，想象两条无限长的链A,B。 p1指向A, p2指向B, p1每次+1， p2每次+2

A: p1-> (1) -- (2) -- (3) -- (4) -- (5) --...
B: p2-> (1) -- (2) -- (3) -- (4) -- (5) --...

因为p2总比p1前进快2倍，所以无论p1在那里，总会有一个时刻，p2 接近p1，
case 1:p1在(2), p2也到达(2), 相遇；
case 2: p1在(2)，p2在(1)。p1+1到达(3), p2+2到达(3)。
所以p2总会与p1相遇。

现在回到这个题目上，一共有三种情况：
1、link1 何link2不相交：p1,p2走到头；p3,p4走到头，结束O(max(m,n))。 m、n分别是link1, link2的长度；
2、link1何link2相交，但无环：p2和p4将在链尾相遇，O(max(m,n)/2) （需要p2与p4作比较）
3、link1何link2相交，且有环：(假设link1无环部分长度s,link2无环部分长度t, 环长r), p1,p2,p3,p4最多经过max(s,t)步进入环，经过最多r/2步，p2先追上p3或者p4先追上p1。O(max(s, t) + r/2)（更正了一下）

所以最坏情况时O(max(m,n)) = O(n)
* 乘以4是因为每步作4次比较。

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)

算法有错。 -holdon(again); 2005-12-7 {251} (#2650330@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 (#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)

哈希表 -benlin(默默向上游); 2005-12-7 {275} (#2650242@0)
1，把链表A放入哈希表，直到出现重复或者链表结束。重复就表示这个链表闭合。
哈希表的插入，应该是lg(n)吧？
2，把链表B放入同一个表，直到出现重复或者链表结束。重复的时候，查看哈希表原有的元素。如果这个元素是链表B的，说明链表B闭合。如果元素是链表A的，说明两表相交。
复杂度： nlgn

我想这应该是他们想要的答案了 -xxjjs(东方射日); 2005-12-7 {246} (#2650300@0)
因为当我说我可以逐个比较，但是我想不是个好办法的时候，他们问我是否知道Big O，同时问我快速排序和冒泡排序的区别时，我说出两者复杂度是N*N和lgN，他们又问那如果排序后再查找呢，我说那会快些，复杂度是NlgN，但是空间复杂度提高了，他们就接入下一个问题.....
一个抽象的算法，你怎么构造这个hash表？ -holdon(again); 2005-12-7 (#2650347@0)

面试中一般只要有一个idea就可以了，不需要详细的实现过程 -xxjjs(东方射日); 2005-12-7 (#2650439@0)

不用这么复杂吧？ -angelscallingme(Angel); 2005-12-8 {541} (#2650906@0)
把a走一遍，并把每个节点的指针记录下来，放在一个container中（可以在插入的时候排序，这样检索以来比较快），如果发现最后有一个指针已经存在，则说明a有环，不用记录了。然后把b走一便，从头到尾，和a一样也哟记录到另一个container中，边记录边比较当前节点的指针是否在a的container中出现过，如果有，则找到，如果到最后b走完了（NULL结束和自己有环）也没有和a任何节点相同的指针，则没有交叉，结束。复杂度应该是n2.

难道我想的太简单了？还是算法过于简陋？但是MS总是出类似智商或脑筋急转弯的编程题，不知道他们要什么样的结果。估计他们只要你的思维方式而不是结果吧？

你这个方法简单是简单了，可不就是复杂度太高了些么？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搜索和比较。 -yuanzidan(原子弹); 2005-12-8 {51} (#2651076@0)
如果不对A/B进行处理，不关用什么算法，都逃不过O(N*N)

此言理论高度不错，有种俯瞰大局的意思。 -akoei(停车**枫林晚); 2005-12-8 (#2651416@0)

根据你的叙述 (加上假定所提供的链表指针不是随意，你并未说明这一点)，从拓扑结构上看，只能逐一比较，UNTIL发现至少一个链表发生循环或X->NEXT == NIL。 -maer(马儿); 2005-12-8 {12} (#2651526@0)
此致
敬礼！
o(2n) -iwantcar(EnjoyStudying); 2005-12-9 {460} (#2652736@0)
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.

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)
#define MYNULL 0X00000001
#define MYNULL2 0X00000002
//SUPPOSE THIS IS 32BIT INTEL COMPUTER. FOR OTHER PROCESSOR, THERE ARE ALWAYS OTHER WAY SIMILARE WAY.

1. go to the end of link1. change the next field of every node to MYNULL when going. remember the address of last node in Var A. NEXT FIELD OF Last node is NULL OR MYNULL for sure.

O(n)

2. from the start of link2 go, change the next field of every node to MYNULL2 when going. if you can find MYNULL . return true.
O(n)

3. return false WHEN SEE NEXT FIELD NULL OR MYNULL2

TOTAL O(2N)

change the next field of every node to MYNULL when going is the key to prevent close loop.

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. -yuanzidan(原子弹); 2005-12-9 {224} (#2653351@0)
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 .

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. -iwantcar(EnjoyStudying); 2005-12-9 {60} (#2654002@0)
It is not always necessary to store things in a linked list.

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", -yuanzidan(原子弹); 2005-12-9 {275} (#2654083@0)
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.

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. -yuanzidan(原子弹); 2005-12-9 {184} (#2654317@0)
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.

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. -iwantcar(EnjoyStudying); 2005-12-9 {84} (#2654674@0)
Ok. I won't discuss this with you any more. I don't need you understand me at all.

your Algorithm is pretty strait-forward, well canadiantire's is little bit tricky though. I was a c programmer years before. I understand what you are talking about very well,dont show off any more please. -yuanzidan(原子弹); 2005-12-10 {644} (#2655161@0)
Creating your own data structure is not worthy here comparing yours with canadiantire's. Assigning/restoring address from your own data type list does cost
time(at least O(several *N )). Further more, setNext method MAY not be available to you. Lists might get constructed by some other public interface/methods.

Regrading "most of data structure is not completely system / language independent", you really need improve your Algorithm concept.

All in all, you create your own data type, consume more spaces, get no time complexity improvements or even worse. And all statements valid only IF you can access the setNext method.

OK, let me rephrase this for you. -canadiantire(轮胎-M.I.N.K.); 2005-12-9 {424} (#2653141@0)
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.

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. -iwantcar(EnjoyStudying); 2005-12-9 {196} (#2653391@0)
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.

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)
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.

1. go to the end of link1. change the next field of every node to MYNULL when going. remember the address of last node in Var A. NEXT FIELD OF Last node is NULL OR MYNULL for sure.

O(n)

2. from the start of link2 go, change the next field of every node to MYNULL2 when going. if you can find MYNULL . return true.
O(n)

3. return false WHEN SEE NEXT FIELD NULL OR MYNULL2

TOTAL O(2N)

change the next field of every node to MYNULL when going is the key to prevent close loop.

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)

@Florida

好像你是对的．能严格证明么？

Replies, comments and Discussions:

More Topics