linked list question

B

Benoît Vertut

user923005 a écrit :
listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.
I was trying to point out that if we are given listA and listB as
above, then the simple "find the node where they meet" strategy is not
going ot produce expected results. If you have some sort of merge
operation, all sorts of strange things might occur.

Consider the following program:

/********************************/
#include <stdio.h>
#include <stdlib.h>

/* Linked-list node structure */
struct node
{
struct node* next;
char data;
};

/* Node instances */
static struct node a = {NULL, 'A'};
static struct node b = {NULL, 'B'};
static struct node c = {NULL, 'C'};
static struct node d = {NULL, 'D'};
static struct node e = {NULL, 'E'};
static struct node f = {NULL, 'F'};
static struct node g = {NULL, 'G'};
static struct node h = {NULL, 'H'};
static struct node i = {NULL, 'I'};
static struct node j = {NULL, 'J'};
static struct node k = {NULL, 'K'};
static struct node l = {NULL, 'L'};
static struct node m = {NULL, 'M'};
static struct node n = {NULL, 'N'};

/* listA has nodes A,B,C,D,E,F,G,L,N,M,I */
struct node* makeListA(void)
{
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next = &l; /* g.next points to l */
l.next = &n;
n.next = &m;
m.next = &i;
i.next = NULL;
return(&a);
}

/* listB has nodes H,I,E,F,G,J,K */
struct node* makeListB(void)
{
h.next = &i;
i.next = &e;
e.next = &f;
f.next = &g;
g.next = &j; /* g.next points to j */
j.next = &k;
k.next = NULL;
return(&h);
}

/* Print all elements of the list (avoid circular lists!) */
void printList(struct node* list)
{
struct node* iter = NULL;
for(iter = list ; iter != NULL ; iter = iter->next)
{
printf("%c ", iter->data);
}
printf("\n");
}

int main(int argc, char* argv[])
{
/* Make listA first, then listB */
{
struct node* listA = makeListA();
struct node* listB = makeListB();
printf("listA: "); printList(listA);
printf("listB: "); printList(listB);
}

printf("\n");

/* Make listB first, then listA */
{
struct node* listB = makeListB();
struct node* listA = makeListA();
printf("listA: "); printList(listA);
printf("listB: "); printList(listB);
}

exit(EXIT_SUCCESS);
}
/********************************/

The output is:
listA: A B C D E F G J K
listB: H I E F G J K

listA: A B C D E F G L N M I
listB: H I

I think you can see here what is confusing people: if you want to consider listA
and listB being defined as you said (respectively A,B,C,D,E,F,G,L,N,M,I and
H,I,E,F,G,J,K), this cannot be done using linked-list structures.

Maybe you were considering that node G can be instanciated two times, let's say
as being declared like
struct node g1 = {NULL, 'G'}, g2 = {NULL, 'G'};
I do not think this was the point of the O/P who wants to "to find out the
addres of the node where the two linked intersect", which I understand as
considering the assertion &g1==&g2, rather than g1.data==g2.data
 
J

James Kuyper

user923005 wrote:
....
Other people have written their little diagrams like this:

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

To show how the two common lists will join together. I was pointing
out that unless D-E-F are identical in both lists and unless there are
no further nodes than F in either list, that strategy is not going to
work.

I guess that what I was saying (apparently with an incredible lack of
communication skill) is that if two list graphs can have different
nodes in them and they might share a common subsequence, it is not
unlikely that they will diverge and do other naughty things that
prevents merger or other useful graph operations.

Several people, including myself, have been assuming that the diagram
above was meant to describe a single set of 9 singly-linked list nodes,
where I.next points to D, and C.next also points to D. You seem to be
talking about two separate sets of 6 list nodes pointing at (or
containing?) 9 distinct pieces of data, where the fourth node of the
first set is distinct from the fourth node of the second set, but that
both nodes point at (or contain?) the same data. I have no idea which
interpretation Richard Heathfield actually intended when he drew his
diagram.
 
R

Richard Bos

Flash Gordon said:
user923005 wrote, On 23/01/08 06:13:

Ah, I think I see the difference of opinion. You are saying if the data
is the same in two different node objects then when merging the lists
you would replace them with a single object. Others have been thinking
that it does not matter what the data is, it only matters if it is
actually the same object appearing in both list.
This means that yours is a harder problem than others have been trying
to solve.

No, what it means is that the problem _as stated_ is not quite clear
enough. It's probably clear to the person who framed it which version is
meant, but without any context, either interpretation is a valid one -
although I'd agree that the "common" interpretation is more likely the
intended one than Dann's.

Richard
 
D

dj3vande

I think you're suffering from a misconception regarding "lists".

user923005 is bright enough, and has a solid enough understanding of
the basics, that I don't think "misconception" is the right word.
I think the problem is that he's talking about equivalence of list
nodes, and everybody else is talking about identity.

If you want to have two lists with the ordering indicated by the
diagram above, you need to have two nodes containing the values I,E,F,G
(since listA needs to have G->L and listB needs G->J, and the common
predecessors need to be distinct to have links to the distinct
successors).

If your comparison is "is this the same node" (checking identity),
you'll never find a duplicate in those lists (since all of their common
values need , while you could if you have lists like:
listC: A,B,C,D,E
listD: F,G,C,D,E
since they have a common tail after some point, and can share the
actual nodes as well as the values (since at C and every step after
that, equivalent nodes have equivalent successors).

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.


dave
 
R

Richard Harter

here is an O(N) solution without tagging or memory allocating tech.
(btw, I personally prefer the tag-the-lsb-bit-of-pointer method, which
is simple and cool.)

first, apply an known algorithm to list A to figure out the last non-
repeated node of it. Note that list A is
either a common single list (tail point to NULL) or list with a cycle.
second, apply the same algorithm to list B to figure out the last non-
repeated node, which actually is the merge node of list A and list B.

There is an error here. When the two lists terminate in a cycle
each list can join the cycle at different nodes. Each is a
legitimate merge node, i.e., we can follow A until it reaches B's
merge point or we can follow B until it reaches A's merge point.
There is no singular "the merge point".

One can argue that the phrasing of the original question
implicitly specified null terminated lists since it used the
wording "the intersection point". Alternatively, we can remove
the ambiguity by adopting some criterion for the "best" merge
point, e.g., the one that minimizes the combined lengths to the
merge point, although this fails if the two merge points are on
exact opposite sides of the cycle.

Even if we rule out cycles, a "good" algorithm should be able to
handle them. As it happens, the second algorithm I posted does
and will produce the "earlier" merge point.
 
F

Flash Gordon

Richard Bos wrote, On 23/01/08 15:43:
No, what it means is that the problem _as stated_ is not quite clear
enough. It's probably clear to the person who framed it which version is
meant, but without any context, either interpretation is a valid one -
although I'd agree that the "common" interpretation is more likely the
intended one than Dann's.

I did not say that the problem as stated was clearly enough, I said that
people were trying to solve different problems.
 
I

Ike Naar

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?
 
C

CBFalconer

Ike said:
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.
 
R

Robert Latest

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
 
R

Robert Latest

user923005 said:
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
 
I

Ike Naar

CBFalconer said:
Ike said:
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.
 
R

Richard Tobin

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.

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
 
B

Ben Bacarisse

Robert Latest said:
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.
 
P

pete

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

pete

pete said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top