Merged linked list in C

clinked list

This question was asked to me in an interview:
There are two header of two linked lists.
There is a merged linked list in c where in the second linked list is merged into the first one at some point.
How could we identify the merging point and what is the complexity of finding that point ?

Could anybody please help?

Best Answer

O(n)

search = list1->header;
if (mixed->header == list1->header) search = list2->header;

while (mixed->next != search) mixed = mixed->next;

Edit: new name for variables and a few comments

/* search is what we want to find. Here it's the head of `list2` */
search = list2->header;
/* unless the merging put `list2` first; then we want to search for `list1` */
if (mixed->header == list2->header) search = list1->header;

/* assume (wrongly) that the header for the mixed list is the merge point */
mergepoint = mixed->head;

/* traverse the mixed list until we find the pointer we're searching */
while (mergepoint->next != search) mergepoint = mergepoint->next;
/* mergepoint now points to the merge point */
Related Topic