linked list question

[user923005]

Ravishankar S said:

<snip>










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.

Consider:
listA: A -- B -- C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I |
\ L
N -- M -- /

Or even:
listA: C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I L


Graph problems have a nasty habit of turning out harder than they
appear at first glance.

If they can itersect, then they can probably also diverge and cycle.
If you don't test for it, funny things can happen, but not "ha-ha"
funny.

 

[Ben Pfaff]

Consider:
listA: A -- B -- C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I |
\ L
N -- M -- /

I don't see how this can happen in a linked list structure. A
linked list node can have only one successor, but your nodes I
and G appear to each have two (E and N, and J and L,
respectively).

 

[CBFalconer]

.... snip ...

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

 

[CBFalconer]

.... snip ...

Consider:
listA: A -- B -- C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I |
\ L
N -- M -- /

Or even:
listA: C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I L

Graph problems have a nasty habit of turning out harder than they
appear at first glance.

If they can itersect, then they can probably also diverge and cycle.
If you don't test for it, funny things can happen, but not "ha-ha"
funny.

Those can't happen. He originally specified singly linked lists.
You have to be able to form and manipulate them from:

struct node {
struct data *datum;
struct node *next;
}

 

[gw7rib]

Ravishankar S said:

<snip>










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.

How about - you measure the length of the lists, subtract one from the
other, and step that number of steps into the longer list. Now step
through each list simultaneously, looking for a match.

Paul.

 

[Peter Nilsson]

How about - you measure the length of the lists, subtract
one from the other, and step that number of steps into the
longer list. Now step through each list simultaneously,
looking for a match.

More formally...

Declare the following variables

LA := length of list A
LB := length of list B
LB' := length of list B if list A is reversed

DA := number of leading nodes distinct to A
DB := number of leading nodes distinct to B
CAB := number of nodes common to A and B

From observation, we have...

LA = DA + CAB
LB = DB + CAB
LB' = DB + DA + 1

Rewritten as...

DA + CAB = LA
DB + CAB = LB
DA + DB = LB' - 1

Which is solved by...

CAB := (LB - LB' + LA + 1)/2
DA := LA - CAB
DB := LB - CAB

The algorithm (including restoration of A from G) is left
as an exercise, but it should be clear that since reverse
and length count are O(N), and we perform a fixed number
of steps of each, the algorithm is O(N + M).

Or I may have forgotten to carry 1 and I'm talking bollocks.

 

[user923005]

I don't see how this can happen in a linked list structure.  A
linked list node can have only one successor, but your nodes I
and G appear to each have two (E and N, and J and L,
respectively).

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

 

[christian.bau]

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 it easily with three loops, not nested. First follow the
linked list from A to the end, finding that the first linked list has
seven elements and ends at G. Then follow the second linked list to
find it has five elements and also ends in G. Since both lists end
with G, they must merge at some point (if they end with different
notes, they definitely don't merge). Since the first list has two
elements more, skip two elements, then go through the lists starting
at C and H and iterate until they meet.

 

[Peter Nilsson]

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

How is G's next link to both L _and_ J?

 

[James Kuyper]

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

Where does I's next pointer point? In ListA, it points nowhere, in
ListB, it points to E.
Where does G's next-pointer point? In ListA, it's L, in listB it's J.

As far as I can see, this can work as a linked list, bu only if the
central loop constitutes a circularly-linked (and therefore infinite)
list, and the three outside portions all link inward, toward the
circular loop. There's two solutions, depending upon whether the central
loop is linked in the clockwise or counter-clockwise direction.

 

[Richard Harter]

Where does I's next pointer point? In ListA, it points nowhere, in
ListB, it points to E.
Where does G's next-pointer point? In ListA, it's L, in listB it's J.

As far as I can see, this can work as a linked list, bu only if the
central loop constitutes a circularly-linked (and therefore infinite)
list, and the three outside portions all link inward, toward the
circular loop. There's two solutions, depending upon whether the central
loop is linked in the clockwise or counter-clockwise direction.

Note that if the lists terminate in a cycle there are some issues
with the simple "determine the lengths of the lists" algorithm,
e.g., you can't simply traverse the lists to their ends. The
second algorithm I posted works okay though.

 

[user923005]

    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^



How is G's next link to both L _and_ J?

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.

 

[user923005]

user923005 wrote:

... snip ...





Those can't happen.  He originally specified singly linked lists.
You have to be able to form and manipulate them from:

    struct node {
       struct data *datum;
       struct node *next;
    }

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
If the lists could be merged, the "afterwards picture" showing the
common parts of the graph would look like my picture.

I was showing that if (after we find the first common node) all the
rest of the nodes are not identical from that point forward, then the
simple y sort of structure is not going to correctly model the data.

 

[user923005]

Where does I's next pointer point? In ListA, it points nowhere, in
ListB, it points to E.

It would depend on how you merged them, because the matching sequences
in the list are not identical from the first match all the way to the
end of the list.

Where does G's next-pointer point? In ListA, it's L, in listB it's J.

It would depend on how you merged them.

As far as I can see, this can work as a linked list, bu only if the
central loop constitutes a circularly-linked (and therefore infinite)
list, and the three outside portions all link inward, toward the
circular loop. There's two solutions, depending upon whether the central
loop is linked in the clockwise or counter-clockwise direction.

The purpose of the diagram was to show that the physical data my not
form the simple Y model for the combined list.

 

[Richard Harter]

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
If the lists could be merged, the "afterwards picture" showing the
common parts of the graph would look like my picture.

I was showing that if (after we find the first common node) all the
rest of the nodes are not identical from that point forward, then the
simple y sort of structure is not going to correctly model the data.

The problem seems to be that what you mean by a node is different
from what every one else means by a node. If I apprehend
correctly everyone else is including the link pointer in the
node, e.g, G can point to only one thing, whereas you are
thinking in terms of the nodes being data separate from the
linkage. (That wording is a mess but I hope you can follow it.)

 

[Flash Gordon]

user923005 wrote, On 23/01/08 06:13:

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.

So how do you get J->next to hold two different values at the same time?
That, I believe, is the point that is being raised. Remember that the
node type will be something like
struck node {
struct node *next;
struct data data;
};

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.

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. So perhaps you think of
the node structure as
struck node {
struct node *next;
struct data *data; /* This is now a pointer */
};

This means that yours is a harder problem than others have been trying
to solve.

 

[Robert Latest]

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 think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

Following your definition of list A, G's next element is L, and I has no
next element.

According to your def of B, there is an element I' whose next element is E,
and another one, G', whose next element is J.

Is it possible, under the condition that both definitions above hold, that
I == I' && G==G'
respectively?

Rhetorical question. The answer is no.

I was trying to point out that if we are given listA and listB as
above,

which isn't possible,

then the simple "find the node where they meet" strategy is not
going ot produce expected results.

....like so often when applying strategies to situations which cannot
exist ;-)

Do yourself a favor and actually try to implement your "convoluted list"
example in C. You'll soon find your conceptual error. You may start with a
typical list element definition like this one:

struct list_node_t {
void *data; /* pointer to payload */
struct list_node_t *next;
} ;

Of course it's possible for the 'data' pointers of nodes in disjunct lists
to point to the same 'payload' memory location (a frequent occurrence in
real code), but that's besides the point.

robert

 

[user923005]

I think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

True, but what if the data does not follow that pattern?

Following your definition of list A, G's next element is L, and I has no
next element.

According to your def of B, there is an element I' whose next element is E,
and another one, G', whose next element is J.

Is it possible, under the condition that both definitions above hold, that
    I == I' && G==G'
respectively?

Rhetorical question. The answer is no.

Look again: I gave the nodes of the two lists:

listA has nodes A,B,C,D,E,F,G,L,N,M,I

listB has nodes H,I,E,F,G,J,K

which isn't possible,

Of course it is.

...like so often when applying strategies to situations which cannot
exist ;-)

Do yourself a favor and actually try to implement your "convoluted list"
example in C. You'll soon find your conceptual error. You may start with a
typical list element definition like this one:

struct list_node_t {
   void *data; /* pointer to payload */
   struct list_node_t *next;

} ;

Of course it's possible for the 'data' pointers of nodes in disjunct lists
to point to the same 'payload' memory location (a frequent occurrence in
real code), but that's besides the point.

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

 

[user923005]

user923005 wrote, On 23/01/08 06:13:







So how do you get J->next to hold two different values at the same time?
That, I believe, is the point that is being raised. Remember that the
node type will be something like
struck node {
    struct node *next;
    struct data data;

};

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. So perhaps you think of
the node structure as
struck node {
    struct node *next;
    struct data *data; /* This is now a pointer */

};

This means that yours is a harder problem than others have been trying
to solve.

If we are searching for a common join point in a graph, I assume that
we are going to do something with it.

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.

 

[guanjun]

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

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.
we play a trick in the second step to make list A appears like a big
cycle as a whole. that is, the code of moving p to the next node
should be like this:
p = (p == last_non_repeated_node_of_list_a) ? head_node_of_list_a : p-

next;

description of the 'known algorithm' (find out the merge node in a
single list with a cycle):
1) let two pointer p1 and p2 point to the head node of the single
list.
2) move forward p1 one node, p2 two nodes. repeat this step until p1
== p2.
3) keep p1 still, and p2 point back to the head node of the single
list.
then move forward p1 and p2 one node each, until they meet.
the node they meet is the merge node of the single list.