Intersection Point /Shared Node between TWO Linked Lists

Two linked list's of size M and size N have a shared node in them. Figure out the shared Node in O(M+N) where M = sizeof(list1) and N = sizeof(list2) using O(1) space.

Strategy:
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.

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: O(m+n).

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

Try extending this solution to N lists, where N > 2