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

142 views
How to find out merge point (node) of two singly linked list ? posted Nov 2, 2014

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;
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. answer Nov 2, 2014

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
Similar Questions