Intersection of Two Linked List | Linked List Data Structure

Problem Statement:

Write a program to find the node at which the intersection of two singly linked lists begins.

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if 
the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as
[5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 
nodes before the intersected node in B.

Solution: Use Hashmap.

first of all create a hashmap, in which we store the nodes of first list.
then iterate over second linked list and search each node of the second linked list
into the hashmap, if we will find the node into hashmap, we will stop here. and store
that node into the solution variable.

Full Code:


  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        map<ListNode*,int>m;
        ListNode* sol=NULL;
        while(headA!=NULL){
            m[headA]=1;
            headA=headA->next;
        }
        while(headB!=NULL){
            if(m.find(headB)!=m.end()){
                auto it = m.find(headB);
                sol = it->first;
                break;
            }
            headB=headB->next;
        }
        return sol;
    }
Conclusion:
Whenever we need to search previous value we should proceed with the hashMap. hashmap will
always an option to solve these kind of problem.