Velocity Reviews > linked list question

Robert Latest
Guest
Posts: n/a

 01-25-2008
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
Guest
Posts: n/a

 01-25-2008
CBFalconer <(E-Mail Removed)> wrote:
>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.

Richard Tobin
Guest
Posts: n/a

 01-25-2008
In article <(E-Mail Removed)>,
http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)> wrote:

> Is there any efficient way of finding the intesection point of two
>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

Observe that the problem is easy if the lists are the same length:
just cdr down them in parallel until you find the common node.

So: determine the length of the lists. Call them l and m, and suppose
l < m (that is, the first list is shorter). Now the tail of the
second list starting after (m-l) elements is the same length as the
first list.

This is of course order N.

-- Richard
--
:wq

Ben Bacarisse
Guest
Posts: n/a

 01-25-2008
Robert Latest <(E-Mail Removed)> writes:

> 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
Guest
Posts: n/a

 01-28-2008
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
Guest
Posts: n/a

 01-28-2008
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