top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find out merge point (node) of two singly linked list ?

+2 votes
580 views
How to find out merge point (node) of two singly linked list ?
posted Nov 2, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

1) Let X be the length of the first linked list until intersection point.
Let Y be the length of the second linked list until the intersection point.
Let Z be the length of the linked list from intersection point to End of
the linked list including the intersection node.
We Have
X + Z = C1;
Y + Z = C2;
2) Reverse first linked list.
3) Traverse Second linked list. Let C3 be the length of second list - 1.
Now we have
X + Y = C3
We have 3 linear equations. By solving them, we get
X = (C1 + C3 – C2)/2;
Y = (C2 + C3 – C1)/2;
Z = (C1 + C2 – C3)/2;
WE GOT THE INTERSECTION POINT.
4) Reverse first linked list.

answer Nov 2, 2014 by Amit Kumar Pandey
0 votes

The second approch would be, just compare the node address one by one. If you found a matching address meas that address is the merge point of two singly linked list.

For example, you can do something like this:

node1, node2;
while(node1) {
      for (;node2; node2 = node2->next) {
         if (node1 == node2) {
               printf("Merge point found\n");
               break;
          }
       }
   node1 = node1->next;
}
answer Nov 3, 2014 by Arshad Khan
...