Y – shaped Linked List. Algorithm to find the node of intersection of two lists.

Problem

Find the node of intersection of 2 lists.

Example:

Solution

Method 1 - Taking advantage of the link list length
Here is the pseudo code to find the node of intersection of 2 lists:

1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list
       ( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node 
   When the 2 nodes are pointing to same node, we found our merge node.

Java code

public static <T> int length(ListNode<T> listHead){
  int listLen = 0;
  ListNode<T> current = listHead;
  while (current != null)
  {
   listLen++;
   current = current.next;
  }
  return listLen;
 }

 public static <T> ListNode<T> 

firstCommonNode(ListNode<T> pList1,ListNode<T> pList2)
 {
  int length1 = length(pList1);
  int length2 = length(pList2);
  
  if (length1 > length2)
  {
   for (int a=0; a < (length1-length2); a++)
   {
    pList1 = pList1.next;
   }
  }
  else
  {
   for (int a=0; a < (length2-length1); a++)
   {
    pList2 = pList2.next;
   }
  }
  while (pList1 != pList2)
  {
   pList1 = pList1.next;
   pList2 = pList2.next;
  } 
  return pList1;
 }

Explanation:
Our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:

First while loop counts the number of nodes in the first list.
Second while loop counts the number of nodes in the second list.
After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.

You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?

Time complexity - O(m+n)
Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).

Method 2 - Create the loop in Y shaped list
 Here is the pseudocode

1)traverse the first list and reach at the end
2)link the end of first list to the head of second list
3) Retain the pointers at the head of both list,also at the end of 1st list
4) Now we have a loop in the linked list, see the image. 
       and we have to find the start of loop, which is 3 in example
5)Take two pointers move 1st by one node,second by two
6) when they meet after that take back the 1st to head
7)Now move both pointers 1st and second also by one node(from the meeting point)
8)where they meet is the intersection of both list
9)break the link from last of 1st list to head of second

You can read on finding the loops in LL here, and eventually method to find the start of the loop.