Intersection Point in Y Shapped Linked Lists

Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other.

Example 1:

Input:

LinkList1 = 3->6->9->common

LinkList2 = 10->common

common = 15->30->NULL

Output: 15

Explanation:

Y ShapedLinked List

Example 2:

Input: 

Linked List 1 = 4->1->common

Linked List 2 = 5->6->1->common

common = 8->4->5->NULL

Output: 8

Explanation: 

4              5

|              |

1              6

 \             /

  8   -----  1 

   |

   4

   |

  5

  |

  NULL 

 

method 1: 

only works for positive data

 c++ implementation:

int intersectPoint(Node* head1, Node* head2)
{
    
   while(head1!=NULL)
   {
       head1->data=-(head1->data);
       head1=head1->next;
   }
   while(head2!=NULL)
   {
      if(head2->data <0)
      return abs(head2->data);
       head2=head2->next;
   }
}

Time Complexity: O(n+m)  

space Complexity: O(1)  

where n and m are the length of both the list

Method 2:

1) Get count of the nodes in the first list, let be c1.

2) Get count of the nodes in the second list, let be c2.

3) Get the difference of counts d = abs(c1 – c2)

4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.

5) Then we can traverse both the lists in parallel till we come across a common node.

c++ implementation:

int intersectPoint(Node* head1, Node* head2)
{
    Node* temp1=head1;int c1=0;
// finding length of list 1
    while(temp1!=NULL)
    {
        c1++;
        temp1=temp1->next;
    }
    
// finding length of list 2
    Node* temp2=head2;int c2=0;
    while(temp2!=NULL)
    {
        c2++;
        temp2=temp2->next;
    }
    
    int d=abs(c1-c2); 
 
         // if list1 is longer, we ignore some of its starting
        // elements till it has as many elements as list2   
    if(c1>c2)
    {
        while(d--)
            head1=head1->next;
     
         // if list1 is longer, we ignore some of its starting
        // elements till it has as many elements as list2  
    }
    else     
    {
        while(d--)
            head2=head2->next;
        // similarly
        // if list2 is longer, we ignore some of its starting
        // elements till it has as many elements as list1
    }
    
        while( head1 != head2 )
    {
        head1 = head1->next;
        head2 = head2->next;
         // now we simple traverse ahead till we get the
        // intersection point, if there is none, this loop
        // will break when both pointers point at NULL
    }
    
    if(head1) 
    return head1->data;
    // if head1 is not NULL, we return its data
    return -1; 
    
}

Time Complexity: O(n)+O(m)+O(n-m) =O(2n)  

space Complexity: O(1)  

where n is length of longer list and m is the length of the shorter list

method 3:

 c++ implementation:

    Node *getIntersectionNode(Node *headA, Node *headB) 
   {
    Node * a=headA;
         Node * b=headB;
        if(a==NULL ||b==NULL)
            return NULL;
        while(a!=b)
        {
            if(a==NULL)
                a=headB;
            else
                a=a->next;
            
             if(b==NULL)
                b=headA;
            else
                b=b->next;   
        }
     return a;
        
    }

Time Complexity: O(n)+O(m)+O(n-m) =O(2n)  

space Complexity: O(1)  

where n is length of longer list and m is the length of the shorter list