Question: There are 2 link lists merging at some node. Find the node, where these 2 lists merge.

Answer: We should have one fact in mind that merging node is found by comparing the address (not value) of the nodes. Since we have 2 different lists, one way is to have 2 for loops and compare addresses of all the possible nodes. This solution is O(mn) where 'm' and 'n' are lengths of given lists.

If length of 2 lists are of equal length, we can traverse both the lists one node at a time and find the common node. But since lengths may not be same, we first find a node in bigger list, from where we have length same as that of smaller list. For this, first we need to find the length of both the lists, then move ahead the difference in bigger list and then match nodes in parallel.

Algorithm:
  1. Find length (len1) of first link list.
  2. Find length (len2) of second link list.
  3. find diff = abs(len1 – len2)
  4. Traverse the bigger list from the first node till 'diff' nodes. Now we have two lists, which have equal no of nodes.
  5. Traverse both the lists in parallel till we come across a common node.

Code:
struct node* findMergeNode(struct node* list1, struct node* list2)
{
  int len1, len2, diff;
  struct node* head1 = list1;
  struct node* head2 = list2;

  len1 = getlength(head1);
  len2 = getlength(head2);
  diff = len1 - len2;

  if (len1 < len2)
  {
      head1 = list2;
      head2 = list1;
      diff = len2 - len1;
  }

  for(int i = 0; i < diff; i++)
      head1 = head1->next;

  while(head1 !=  NULL && head2 != NULL)
  {
      if(head1 == head2)
          return head1->data;
      head1= head1->next;
      head2= head2->next;
  }

  return NULL;
}

Complexity: Complexity of above solution is O(m+n).

PS: Even if the lists don't merge at any intermediate point, they will always merge at NULL node in the end.

PPS: Try extending this solution to N lists, where N > 2.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.