linked list question

[junky_fellow]

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

[CBFalconer]

Ike Naar wrote:

ju**********@ya hoo.co.in <ju**********@y ahoo.co.inwrote :

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

Reverse both lists and compare the reversed lists?

Initial lists:

list1: A --B --C -\
\
--D --E
/
list2: X --Y -------/

Reverse list1 and get: (remember Ys next ptr unchanged)

list1: E -------------\
\
--D --C --B --A
/
list2: X --Y -------/

Now reverse list2 and get: (Es next ptr unchanged)

list1: E --------------\
\
--D --Y --X
/
list2: A --B --C --/

=============== =============== ============
However, if we first reverse list2, we get:

list1: A --B --C -\
\
--D --Y --X
/
list2: E -------------/

Now reverse list1 and get:

list1: X --Y -------\
\
--D --C --B --A
/
list2: E -------------/

and I cannot see what is common to the two double reversals that
identifies the original node C (or Y), nor the reversal steps need
to regain the original configuration.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[Robert Latest]

dj******@csclub .uwaterloo.ca.i nvalid wrote:

If your comparison is "does this node have the same value" (checking
equivalence), you'll find a match in I-E-F-G in the original example as
well as in C-D-E in the simpler example.

Yes, but if we talk about "values" (or "payloads", as I like to call them)
of lists then the OP should have said so. I'm doubtful that he gets the
difference.

robert

[Robert Latest]

user923005 wrote:

Believe it or not, I have written successful lists and graphs.

I believe you when you show us a small example of crossing-over linked
lists.

robert

[Ike Naar]

CBFalconer <cb********@mai neline.netwrote :

>Ike Naar wrote:

>Reverse both lists and compare the reversed lists?

Initial lists:

list1: A --B --C -\
\
--D --E
/
list2: X --Y -------/

[snipped: in-place place reveral list1 and list2]

and I cannot see what is common to the two double reversals that
identifies the original node C (or Y), nor the reversal steps need
to regain the original configuration.

What I actually meant to say (and I did not make myself very clear) was:
produce a reversed _copy_ of each list, and compare the reversed copies,

list1: A B C D E reversed copy of list1: E D C B A
list2: X Y D E reversed copy of list2: E D Y X
common prefix of reversed copies: E D

A far more elegant solution has been posted elsethread:
Make sure both lists have equal length, by trimming the head part of
the longest list; then find the first common element of the resulting
lists.

[Ben Bacarisse]

Robert Latest <bo*******@yaho o.comwrites:

user923005 wrote:

>Believe it or not, I have written successful lists and graphs.

I believe you when you show us a small example of crossing-over linked
lists.

I think that dcorbit is talking about lists in which the content is
pointed to by, rather than contain in, the nodes. I C:

struct list_node {
struct list_node *next;
Content *content; /* void * if one wants to be generic */
};

With this structure, two lists may share data so that diagrams in
which some items are common to multiple lists are then possible.

--
Ben.

[pete]

CBFalconer wrote:

>
Richard Heathfield wrote:

... snip ...

Indeed. Consider these linked lists:

listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I

You can scan through the lists. Do so, retaining L as the length
of listA, and L1 as the length of listB. Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7. I think you can now find
the location of item E in either list.

If the first node of listA is node number (0),
then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

--
pete

[pete]

pete wrote:

>
CBFalconer wrote:

Richard Heathfield wrote:

>

... snip ...

>
Indeed. Consider these linked lists:
>
listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I

You can scan through the lists. Do so, retaining L as the length
of listA, and L1 as the length of listB. Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7. I think you can now find
the location of item E in either list.

If the first node of listA is node number (0),
then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

That would be after listA has been reversed again.

--
pete