链表问题 [英] linked list question
问题描述
有没有找到两个
单链表的截面点的有效方法？
我意思是说，有两个单链表，他们会在某一点见到
。我想找出两个
链接相交的节点的地址。
感谢您的帮助...
< ju ********** @ yahoo.co.inwrote in message
news：3d ********************************** @ e4g2000h sg.googlegroups.com ...
是否有任何有效的方法可以找到两个
单链表的交叉点？
我的意思是说，有两个单链表，他们在
见面。我想找出两个
链接相交的节点的地址。
感谢任何帮助......
你的意思是链接列表的合并点？我不能成像交叉
单独链接
p = listA;
q = listB;
while （p& q）{
if（p-> next == q-> next）break;
p = p-> next;
q = q-> next;
}
if（p&& q&&（p- > next == q-> next））
{
printf（" Merging point found found \ n）;
}
但要小心：我还没有测试过代码！
Ravishankar S说：
< snip>
你的意思是链接列表的合并点？我无法成像十字路口
单独链接
p = listA;
q = listB;
而（p&& q）{
if（p-> next == q-> next）break;
p = p-> next;
q = q-> next;
}
if（p&& q &&（p-> next == q-> next））
{
printf（" Merging point found found \\\
"）; < br $>
}
但要小心：我还没有测试过代码！
的确如此。考虑这些链接列表：
listA：A - B - C - D
\
E - F - G
/
listB：H - 我
您将A与H，B与I，C进行比较带E，D带F，E带G.现在循环
停止，q为NULL。你完全错过了合并点。
我相信这必须在两个嵌套循环中完成（或者至少，好像它
是两个嵌套循环！ - 即O（listAnodecount * listBnodecount）），但我会很高兴被证明是错误的。
-
Richard Heathfield< http://www.cpax.org.uk>
电子邮件：-http：// www。 + rjh @
谷歌用户：< http://www.cpax.org.uk/prg/writings/googly.php>
Usenet是一个奇怪的放置" - dmr 1999年7月29日
Richard Heathfield< rj*@see.sig.invalidwrites：
Ravishankar S说：
< snip>
你的意思是链接列表的合并点？我无法成像十字路口
单独链接
p = listA;
q = listB;
而（p&& q）{
if（p-> next == q-> next）break;
p = p-> next;
q = q-> next;
}
if（p&& q &&（p-> next == q-> next））
{
printf（" Merging point found found \\\
"）; < br $>
}
但要小心：我还没有测试过代码！
的确如此。考虑这些链接列表：
listA：A - B - C - D
\
E - F - G
/
listB：H - 我
您将A与H，B与I，C进行比较带E，D带F，E带G.现在循环
停止，q为NULL。你完全错过了合并点。
我相信这必须在两个嵌套循环中完成（或者至少，好像它
是两个嵌套循环！ - 即O（listAnodecount * listBnodecount）），但我会很高兴被证明是错误的。
如果你接受在O（listAnodecount + listBnodecount）中分配
内存，你可以做O（listAnodecount + listBnodecount）：build反向列表
引用原文，然后迭代它们直到它们发散。
-
Jean-Marc
Hi,
Is there any efficient way of finding the intesection point of two
singly linked lists ?
I mean to say that, there are two singly linked lists and they meet at
some point. I want to find out the addres of the node where the two
linked intersect.
thanks for any help...
<ju**********@yahoo.co.inwrote in message
news:3d**********************************@e4g2000h sg.googlegroups.com...Hi,
Is there any efficient way of finding the intesection point of two
singly linked lists ?
I mean to say that, there are two singly linked lists and they meet at
some point. I want to find out the addres of the node where the two
linked intersect.
thanks for any help...you mean point of merge of linked list ? i cannot imaging "intersection" of
singly linked
p = listA;
q = listB;
while(p && q) {
if(p->next == q->next) break;
p = p->next;
q = q->next;
}
if(p && q && (p->next == q->next))
{
printf("Merging point found\n");
}
But careful: I have not tested the code !
Ravishankar S said:
<snip>
you mean point of merge of linked list ? i cannot imaging "intersection"
of singly linked
p = listA;
q = listB;
while(p && q) {
if(p->next == q->next) break;
p = p->next;
q = q->next;
}
if(p && q && (p->next == q->next))
{
printf("Merging point found\n");
}
But careful: I have not tested the code !Indeed. Consider these linked lists:
listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I
You compare A with H, B with I, C with E, D with F, E with G. Now the loop
stops, and q is NULL. You missed the merge point completely.
I believe this has to be done in two nested loops (or at least, "as if" it
were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I''d
be delighted to be proved wrong.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Richard Heathfield <rj*@see.sig.invalidwrites:
Ravishankar S said:
<snip>
you mean point of merge of linked list ? i cannot imaging "intersection"
of singly linked
p = listA;
q = listB;
while(p && q) {
if(p->next == q->next) break;
p = p->next;
q = q->next;
}
if(p && q && (p->next == q->next))
{
printf("Merging point found\n");
}
But careful: I have not tested the code !
Indeed. Consider these linked lists:
listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I
You compare A with H, B with I, C with E, D with F, E with G. Now the loop
stops, and q is NULL. You missed the merge point completely.
I believe this has to be done in two nested loops (or at least, "as if" it
were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I''d
be delighted to be proved wrong.You can do O(listAnodecount+listBnodecount) if you accept to allocate
memory in O(listAnodecount+listBnodecount) as well: build reversed lists
referencing the original and then iterate on them until they diverge.
--
Jean-Marc
这篇关于链表问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
