A
Army1987
Then it isn't a linked list.user923005 said:True, but what if the data does not follow that pattern?
Then it isn't a linked list.user923005 said:True, but what if the data does not follow that pattern?
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.
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.
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.
I think you're suffering from a misconception regarding "lists".
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.
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.
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.
Ike said:Reverse both lists and compare the reversed lists?
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.
user923005 said:Believe it or not, I have written successful lists and graphs.
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.
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.
Robert Latest said:I believe you when you show us a small example of crossing-over linked
lists.
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.
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.
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.