1. Home
  2. Finding the intersection point using Hashing

Finding the intersection point using Hashing

Basically, we need to find a common node of two linked lists. So, we store all the nodes of the first list in a hash set and then iterate over second list checking if the node is present in the set. If we find a node which is present in the hash set, we return the node.

Step-by-step approach:

  • Create an empty hash set.
  • Traverse the first linked list and insert all nodes’ addresses in the hash set.
  • Traverse the second list. For every node check if it is present in the hash set. If we find a node in the hash set, return the node.

Below is the implementation of the above approach:

C++ 
// C++ program to get intersection point of two linked list
#include <iostream>
#include <unordered_set>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
     Node(int d)
    {
      data = d;
      next = NULL;
    }
};

// function to find the intersection point of two lists
void MegeNode(Node* n1, Node* n2)
{
    unordered_set<Node*> hs;
    while (n1 != NULL) {
        hs.insert(n1);
        n1 = n1->next;
    }
    while (n2) {
        if (hs.find(n2) != hs.end()) {
            cout << n2->data << endl;
            break;
        }
        n2 = n2->next;
    }
}

// function to print the list
void Print(Node* n)
{
      Node* curr = n;
      while(curr != NULL){
      cout << curr->data << " ";
      curr = curr->next;
    }
      cout << endl;
}
  
int main() 
{
     // list 1
     Node* n1 = new Node(1);
     n1->next = new Node(2);
     n1->next->next = new Node(3);
     n1->next->next->next = new Node(4);
     n1->next->next->next->next = new Node(5);
     n1->next->next->next->next->next = new Node(6);
     n1->next->next->next->next->next->next = new Node(7);
     // list 2
     Node* n2 = new Node(10);
     n2->next = new Node(9);
     n2->next->next = new Node(8);
     n2->next->next->next = n1->next->next->next;
     Print(n1);
     Print(n2);
          
       MegeNode(n1,n2);
      
       return 0;
}

 // This code is contributed by Upendra
Java 
// Java program to get intersection point of two linked list
import java.util.*;
class Node {
    int data;
    Node next;
    Node(int d)
    {
        data = d;
        next = null;
    }
}
class LinkedListIntersect {
    public static void main(String[] args)
    {
        // list 1
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);
        n1.next.next.next = new Node(4);
        n1.next.next.next.next = new Node(5);
        n1.next.next.next.next.next = new Node(6);
        n1.next.next.next.next.next.next = new Node(7);
        // list 2
        Node n2 = new Node(10);
        n2.next = new Node(9);
        n2.next.next = new Node(8);
        n2.next.next.next = n1.next.next.next;
        Print(n1);
        Print(n2);
        System.out.println(MegeNode(n1, n2).data);
    }

    // function to print the list
    public static void Print(Node n)
    {
        Node cur = n;
        while (cur != null) {
            System.out.print(cur.data + "  ");
            cur = cur.next;
        }
        System.out.println();
    }

    // function to find the intersection of two node
    public static Node MegeNode(Node n1, Node n2)
    {
        // define hashset
        HashSet<Node> hs = new HashSet<Node>();
        while (n1 != null) {
            hs.add(n1);
            n1 = n1.next;
        }
        while (n2 != null) {
            if (hs.contains(n2)) {
                return n2;
            }
            n2 = n2.next;
        }
        return null;
    }
}
Python3 
# Python program to get intersection 
# point of two linked list
class Node :
    def __init__(self, d):
        self.data = d;
        self.next = None;

# Function to print the list
def Print(n):
    cur = n;
    while (cur != None) :
        print(cur.data, end=" ");
        cur = cur.next;
    print("");

# Function to find the intersection of two node
def MegeNode(n1, n2):
    
    # Define hashset
    hs = set();

    while (n1 != None):
        hs.add(n1);
        n1 = n1.next;
    while (n2 != None):
        if (n2 in hs):
            return n2;
        n2 = n2.next;
    
    return None;


# Driver code

# list 1
n1 = Node(1);
n1.next = Node(2);
n1.next.next = Node(3);
n1.next.next.next = Node(4);
n1.next.next.next.next = Node(5);
n1.next.next.next.next.next = Node(6);
n1.next.next.next.next.next.next = Node(7);

# list 2
n2 = Node(10);
n2.next = Node(9);
n2.next.next = Node(8);
n2.next.next.next = n1.next.next.next;

Print(n1);
Print(n2);

print(MegeNode(n1, n2).data);

# This code is contributed by _saurabh_jaiswal
C# 
// C# program to get intersection point of two linked list
using System;
using System.Collections.Generic; 

public class Node 
{
    public int data;
    public Node next;
    public Node(int d)
    {
        data = d;
        next = null;
    }
}
public class LinkedListIntersect
{
    public static void Main(String[] args)
    {
        // list 1
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);
        n1.next.next.next = new Node(4);
        n1.next.next.next.next = new Node(5);
        n1.next.next.next.next.next = new Node(6);
        n1.next.next.next.next.next.next = new Node(7);
        // list 2
        Node n2 = new Node(10);
        n2.next = new Node(9);
        n2.next.next = new Node(8);
        n2.next.next.next = n1.next.next.next;
        Print(n1);
        Print(n2);
        Console.WriteLine(MegeNode(n1, n2).data);
    }

    // function to print the list
    public static void Print(Node n)
    {
        Node cur = n;
        while (cur != null) 
        {
            Console.Write(cur.data + " ");
            cur = cur.next;
        }
        Console.WriteLine();
    }

    // function to find the intersection of two node
    public static Node MegeNode(Node n1, Node n2)
    {
        // define hashset
        HashSet<Node> hs = new HashSet<Node>();
        while (n1 != null) 
        {
            hs.Add(n1);
            n1 = n1.next;
        }
        while (n2 != null)
        {
            if (hs.Contains(n2)) 
            {
                return n2;
            }
            n2 = n2.next;
        }
        return null;
    }
}

// This code is contributed by 29AjayKumar
Javascript 
// Javascript program to get intersection 
// point of two linked list
class Node 
{
    constructor(d)
    {
        this.data = d;
        this.next = null;
    }
}

// Function to print the list
function Print(n)
{
    let cur = n;
    while (cur != null) 
    {
       console.log(cur.data + "  ");
        cur = cur.next;
    }
  console.log("<br>");
}

// Function to find the intersection of two node
function MegeNode(n1, n2)
{
    
    // Define hashset
    let hs = new Set();
    while (n1 != null)
    {
        hs.add(n1);
        n1 = n1.next;
    }
    while (n2 != null)
    {
        if (hs.has(n2))
        {
            return n2;
        }
        n2 = n2.next;
    }
    return null;
}

// Driver code

// list 1
let n1 = new Node(1);
n1.next = new Node(2);
n1.next.next = new Node(3);
n1.next.next.next = new Node(4);
n1.next.next.next.next = new Node(5);
n1.next.next.next.next.next = new Node(6);
n1.next.next.next.next.next.next = new Node(7);

// list 2
let n2 = new Node(10);
n2.next = new Node(9);
n2.next.next = new Node(8);
n2.next.next.next = n1.next.next.next;

Print(n1);
Print(n2);

console.log(MegeNode(n1, n2).data);

// This code is contributed by rag2127

Output
1 2 3 4 5 6 7 
10 9 8 4 5 6 7 
4

Time complexity: O(n), where n is the length of the longer list. This is because we need to traverse both of the linked lists in order to find the intersection point.
Auxiliary Space: O(n) , because we are using unordered set.

Write a function to get the intersection point of two Linked Lists

There are two singly linked lists in a system. By some programming error, the end node of one of the linked lists got linked to the second list, forming an inverted Y-shaped list. Write a program to get the point where two linked lists merge. 

Intersection Point of Two Linked Lists


The above diagram shows an example with two linked lists having 15 as intersection points.

Recommended Problem
Intersection Point in Y Shapped Linked Lists
Solve Problem

Similar Reads

Finding the intersection point using two Nested Loops:

Use 2 nested for loops. The outer loop will be for each node of the 1st list and the inner loop will be for the 2nd list. In the inner loop, check if any of the nodes of the 2nd list is the same as the current node of the first linked list. The time complexity of this method will be O(M * N) where m and n are the numbers of nodes in two lists....

Finding the intersection point using Hashing:

Basically, we need to find a common node of two linked lists. So, we store all the nodes of the first list in a hash set and then iterate over second list checking if the node is present in the set. If we find a node which is present in the hash set, we return the node....

Find the intersection point using difference in node counts:

In this method, we find the difference (D) between the count of nodes in both the lists. Then, we increment the start pointer of the longer list by D nodes. Now, we have both start pointers at the same distance from the intersection point, so we can keep incrementing both the start pointers until we find the intersection point....

Find the intersection point using Two Pointer Technique:

This algorithm works by traversing the two linked lists simultaneously, using two pointers. When one pointer reaches the end of its list, it is reassigned to the head of the other list. This process continues until the two pointers meet, which indicates that they have reached the intersection point....

Find the intersection point by making a loop in the first list:

In this algorithm, we make the first list circular by connecting the last node to the first node. Then we take the size of the loop and move the first pointer in the second linked list by that number of nodes. Then take another pointer from the beginning of the second list and increment first and second pointer simultaneously to find the intersection point....

Categories

HTML CSS3 Bootstrap Foundation Sass JavaScript TypeScript JQuery AngularJS React NodeJS Highcharts PHP Python Python3 Django Linux Docker Ruby Java C C ++ Perl Servlet JSP Lua Scala Go ASP C # SQL MySQL SQLite MongoDB Redis Android Swift ionic Kotlin XML tutorial

Contact US