Logo
×

Intersection Point of two linked list in Java

In this article, you will be very well acknowledged about how to achieve the intersection point of two linked list in Java. There are several approaches to obtain. Surely each and every one of them will be discussed in this article. This is an important topic from the interview point of view.

Initially let us know about the linked list

Linked List

The Collection framework found in the java.util package includes Linked List. This class is an application of a LinkedList data structure, a sequential data structure where each component is a unique object with both a data part as well as address portion and is not kept in a single location. Pointers and addresses are used to connect the elements. Every element is referred to as a node.

Types of Approaches

There are several approaches that obtain the intersection point of two linked lists. They are

  • Implementing Two Lops
  • Based on Node Density
  • The Hashing Method
  • The Two Pointer Method
  • Making a Circular First Linked List

Let us go through each one of them with a brief description and an example program as well.

Implementing two loops

Employ two nested for loops. Each node in the first list will be covered by the outer loop, while the second list will be covered by the inner loop. Check in the internal loop to see whether any of these nodes from the second list are identical to the node that is currently in the initial linked list. The method's time complexity will be O(M * N), while m and n are just the total nodes in the two lists.

Let us go through the program execution. Let the two linked lists be as follows:

List1: [2, 4, 6, 8]

List2: [3, 6, 8]

File name: Twoloops.java

// A Java program that determines the intersection of two linked lists
class Twoloops {


static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public Node getIntersectionNode(Node head1, Node head2)
{
while (head2 != null) {
Node temp = head1;
while (temp != null) {
// when both Nodes are identical
if (temp == head2) {
return head2;
}
temp = temp.next;
}
head2 = head2.next;
}
// Returns NULL if there is no intersection between the lists.
return null;
}


public static void main(String[] args)
{
Twoloops list = new Twoloops();
                          Node head1, head2;
                          head1 = new Node(0);
head2 = new Node(3);


Node newNode = new Node(2);
head2.next = newNode;


newNode = new Node(4);
head2.next.next = newNode;


newNode = new Node(6);
head1.next = newNode;
head2.next.next.next = newNode;


newNode = new Node(8);
head1.next.next = newNode;


head1.next.next.next = null;


Node intersectionPoint
= list.getIntersectionNode(head1, head2);


if (intersectionPoint == null) {
System.out.print(" There exist no intersection point \n");
}
else {
System.out.print("The intersection point is: "
+ intersectionPoint.data);
}
}
}

Output

The intersection point is: 6

Based on Node Density

Count the total number of nodes in the initial linked list, c1 in our scenario, which is present. tally the number of elements in the next linked list—c2 in our case—which is present. The differences between the counts c1 and c2 should be determined and stored in a variable called diff in this instance. Beginning with I = 0, create a loop that iterates through the first linked list's nodes until it reaches diff. Start simultaneously exploring both linked lists at this point. The value of the common node is returned when we obtain it. If null is detected, -1 may be returned, denoting that there is no intersection point between the two linked lists.

Let us go through the program execution for understanding. Let the two lists be as follows:

List1: [0, 2, 4, 6, 8]

List2: [3, 6, 8]

File name: Basedoncount.java

// Java program to determine where two linked lists overlap

class Basedoncount {


static Node head1, head2;


static class Node {


int data;
Node next;


Node(int d)
{
data = d;
next = null;
}
}
int getNode()
{
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;


if (c1 > c2) {
d = c1 - c2;
return _getIntesectionNode(d, head1, head2);
}
else {
d = c2 - c1;
return _getIntesectionNode(d, head2, head1);
}
}
int _getIntesectionNode(int d, Node node1, Node node2)
{
int i;
Node current1 = node1;
Node current2 = node2;
for (i = 0; i < d; i++) {
if (current1 == null) {
return -1;
}
current1 = current1.next;
}
while (current1 != null && current2 != null) {
if (current1.data == current2.data) {
return current1.data;
}
current1 = current1.next;
current2 = current2.next;
}


return -1;
}
int getCount(Node node)
{
Node current = node;
int count = 0;


while (current != null) {
count++;
current = current.next;
}


return count;
}


public static void main(String[] args)
{
Basedoncount list = new Basedoncount();


// initial linked list creation
list.head1 = new Node(0);
list.head1.next = new Node(2);
list.head1.next.next = new Node4);
list.head1.next.next.next = new Node(6);
list.head1.next.next.next.next = new Node(8);


// second linked list creation
list.head2 = new Node(3);
list.head2.next = new Node(6);
list.head2.next.next = new Node(8);


System.out.println("The intersection point is " + list.getNode());
}
}

Output

The intersection point  is 6

The Hashing Method

In order to store the integers, make a HashSet.

open a loop that will iterate across the initial linked list. Put every node from the initial linked list into the HashSet that was produced during the initial step. launch a loop to iterate through the next linked list. Verify if the data of the node referred to in each traversal is contained in the HashSet. If it is, stop the loop right away and give the value back. The intersection of a linked list doesn't really occur if the loop's iterations have reached their limit.

Let us understand it with a basic example program

List1: [0, 2, 4, 6, 8]

List2: [3, 6, 8]

File name: Hash.java

// Java program to get intersection point of two linked list
import java.util.*;
class Hash {
int data;
Node next;
Hash(int d)
{
data = d;
next = null;
}
}
class LinkedListIntersect {
public static void main(String[] args)
{
// list 1
             Hash n1 = new Hash(0);
n1.next = new Hash(2);
n1.next.next = new Hash(4);
n1.next.next.next = new Hash(6);
n1.next.next.next.next = new Hash(8);

// list 2
Hash n2 = new Hash(3);
n2.next = new Hash(6);
n2.next.next = new Hash(8);
n2.next.next.next = n1.next.next.next;


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;
}
}

Output

6

The Two Pointer method

Employing two points

  • Two pointers, ptr1 and ptr2, should be initialised at head1 and head2.
  • Each node at a time, navigate the lists.
  • Redirect ptr1 to head2 when it comes to the conclusion of a list.
  • Similar to this, send ptr2 to head1 when it arrives at the end of the  list.
  • They will be equally separated from the collision point once they have both completed the reassignment process.
  • The intersection node is any node where ptr1 and ptr2 intersect.
  • Whenever there is no intersecting node at the end of the second iteration, NULL is returned.

Let us understand it with an example program

List1: [0, 2, 4, 6, 8]

List2: [3, 6, 8]

File name: Twopointer.java

// Java code that prints list intersections
import java.util.*;
class Twopointer{
static class Node {
int data;
Node next;
};


// A tool that returns the intersection node
static Node intersectPoint(Node head1, Node head2)
{
Node ptr1 = head1;
Node ptr2 = head2;


// Whenever a head is empty
if (ptr1 == null || ptr2 == null) {


return null;
}


// Explore the lists until you come to the intersection node.
while (ptr1 != ptr2) {


ptr1 = ptr1.next;
ptr2 = ptr2.next;





if (ptr1 == ptr2) {


return ptr1;
}
// They will be equally separated from the meeting point once they have both //completed the reassignment process.
if (ptr1 == null) {


ptr1 = head2;
}

if (ptr2 == null) {


ptr2 = head1;
}
}


return ptr1;
}


// The method prints the intersection nodes in the specified linked list
static void print(Node node)
{
if (node == null)
System.out.print("null");
while (node.next != null) {
System.out.print(node.data+ ".");
node = node.next;
}
System.out.print(node.data);
}


public static void main(String[] args)
{



Node newNode;
Node head1 = new Node();
head1.data = 3;
Node head2 = new Node();
head2.data = 0;
newNode = new Node();
newNode.data = 2;
head2.next = newNode;
newNode = new Node();
newNode.data = 4;
head2.next.next = newNode;
newNode = new Node();
newNode.data = 6;
head1.next = newNode;
head2.next.next.next = newNode;
newNode = new Node();
newNode.data = 8;
head1.next.next = newNode;
head1.next.next.next = null;
Node intersect_node = null;


// Determine the node at which two linked lists intersect.
intersect_node = intersectPoint(head1, head2);


System.out.print("The point of intersection:");


print(intersect_node);
}
}

Output

The point of intersection:6

Making a Circular First Linked List

Let us learn how the circular first linked list works in achieving the intersection point of two linked lists.

  • Construct a loop that will iterate across the initial linked list. Continue until the first linked list's final node. Record the number of nodes with in linked list as you traverse it and save the result in a variable, in this instance countNode. The final node of linked list should also be saved in a variable.
  • Create a link from the list's end node to its beginning node. in order to create a round linked list.
  • Utilize a pointer, in our example p2, to traverse that many nodes in the secondary linked list since the size of the initial linked list has already been known.
  • start a new pointer from the second linked list's head (h2).
  • Using a loop, advance h2 and p2 each node at a time. (p2!= h2) ought to be the loop's breaking condition. The initial point of intersection of the provided two linked list occurs where the p2 and h2 collide.
  • Make the first linked list's final node point to null. By eliminating the loop inside the linked list, the whole first linked list returns to its initial state in this manner.

Let us understand the below program.

List1: [0, 2, 4, 6, 8]

List2: [3, 6, 8]

File name: Circular.java

import java.util.*;  
  public class Circular 
{  
  
static LinkedListNode h1, h2;  
  
static class LinkedListNode   
{  
  
int d;  
LinkedListNode nxt;  
  
LinkedListNode(int d)  
{  
this.d = d;  
nxt = null;  
}  
}  
  
static LinkedListNode intersectionPoint(LinkedListNode h1, LinkedListNode h2)  
{  
LinkedListNode p1 = h1;  
LinkedListNode p2 = h2;  
  
if (p1 == null || p2 == null)   
{  
  return null;  
}  
  
// a variable for holding track of the nodes' number
int countNodes = 0;  
  
// travelling until the last node
while(p1.nxt != null)  
{  
p1 = p1.nxt;     
countNodes = countNodes + 1;  
}  
  
  
// calculating the last node
countNodes = countNodes + 1;  
  
// creating a cyclic linked list from the initial linked list
p1.nxt = h1;  
  
  while(countNodes != 0)  
{  
countNodes = countNodes - 1;  
p2 = p2.nxt;  
}  
  
  
// We now shift h2 from the start and p2 from its existing position.
while(h2 != p2)  
{  
h2 = h2.nxt;  
p2 = p2.nxt;  
}  
  
//  list restoring those modifications and converting it into the linear linked
p1.nxt = null;  
  
return h2;  
}  
  
  
// a process for showing the values of a linked list's nodes
void displayNodes(LinkedListNode l1)  
{  
while(l1 != null)  
{  
System.out.print(l1.d + " ");  
l1 = l1.nxt;  
}  
}  
// main method  
public static void main(String[] argvs)  
{  


Circular list = new Circular();  
  
list.h1 = new LinkedListNode(0);  
list.h1.nxt = new LinkedListNode(2);  
list.h1.nxt.nxt = new LinkedListNode(4);  
list.h1.nxt.nxt.nxt = new LinkedListNode(6);  
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(8);  
  


list.h2 = new LinkedListNode(3);  
list.h2.nxt = list.h1.nxt.nxt.nxt;  
  
LinkedListNode intersectNode = null;  
  
System.out.println("The first linked list is: ");  
list.displayNodes(list.h1);  
System.out.println();  
  
  
System.out.println("The second linked list is: ");  
list.displayNodes(list.h2);  
System.out.println();  
  
// detecting the first intersection point between the two linked lists
intersectNode = intersectionPoint(h1, h2);  
  
  
if(intersectNode != null)  
{  
System.out.println("The first intersection point of the linked lists is: " + intersectNode.d);  
}  
else  
{  
System.out.println("The first intersection point of the linked lists does not exist. ");      
}  
}  
}  

Output

The first intersection point of the linked lists is: 6

Related Topics

Program to find the duplicate characters in a string

Problem statement You have given with a string and your task is to find out the repeated characters from the string and print them. If no character is repeated, then you...

2 minutes read.

Sierpinski Number in Java

The Sierpinski triangle—is it a fractal? The Sierpinski Triangle fractals. A self-similar fractal is the Sierpinski triangle. It is made of an equilateral triangle with its residual area successively reduced by...

3 minutes read.

Java String length() method

Java String length() method returns length of the characters in a String. Syntax: public int length() Returns It returns length of the characters Java String length() method example 1          public class JavaStringLengthEx1  ...

1 minute read.

Example of Static import in Java

Static keyword Java's static keyword is mainly used to control memory. Variables, methods, blocks, and nested classes are compatible with the static keyword. Instead of an instance, the static keyword is...

3 minutes read.

User Defined Custom Exceptions in Java

In this tutorial, we will discuss user-defined custom exceptions with examples. Introduction In Java, we have proactively characterised, Exception classes, for example, ArithmeticException, NullPointerException, ArrayoutOfBound and so on. These built-in exceptions are...

3 minutes read.

Various operations on the Queue using Stack in Java

The Java Collections Framework's core data structures are the Stack and Queue. They are used to store and retrieve identical data in a presentation sequence. These two linear data structures...

7 minutes read.

How to Convert int to long in Java

How to Convert int to long in Java When two variables of different types are involved in the single expression, Java compiler uses built-in library function to convert the variable to...

2 minutes read.

Checked vs Unchecked Exceptions in Java

In this tutorial, we will discuss Java's checked and unchecked Exceptions. Exception An exception is an undesirable event that disrupts the normal flow of the program. An exception is thrown at runtime. It...

4 minutes read.

Differences between Byte Code and Machine Code

This tutorial will discuss the differences between Byte Code and Machine Code. Before that, let's try to know what byte and machine code is. Introduction Every computer has a set of instructions...

4 minutes read.

Java Speech Recognition

The customer experience and convenience are improved with its utilization. Command and control interest in buying and voice synthesizers are supported by the cross-platform API defined by the API. For...

4 minutes read.

public static void main string args meaning in java

In java main() method is the initial point for execution of the program. If a program doesn’t contain the main method, the program will not execute. JVM(java virtual machine) starts...

3 minutes read.

Rotate matrix by 90 degrees in Java | Rotate matrix in Java clockwise and anti-clockwise

In this article, you will be acknowledged about what is a matrix along with an example. Most importantly you will be equipped knowledge on how to rotate the matrix by...

4 minutes read.

Matrix Multiplication Program in Java

Matrix Multiplication Program in Java The matrix multiplication program in Java is the continuation of the matrix program in Java that we have already discussed earlier. In this section, we will...

3 minutes read.

Program to Reverse a Number in Java

In order to reverse a number, the digit in the first place must be swapped with the digit in the final position, the second digit with the second-to-last digit, and...

3 minutes read.

Java Transient Keyword

An object in Java can be turned into a stream of bytes using serialization. The data of the instance and the kind of data saved in that instance are both...

3 minutes read.

Java Char Keyword

The java char keyword is a data type which is defined as character data type.Char keyword belongs to a primitive data type where the data types are classified into primitive...

4 minutes read.

Java String vs StringBuffer

Java String vs StringBuffer In this section, we will discuss the key differences between String and StringBuffer class. Before moving to the ahead in this section, let’s introduce with both classes. String...

4 minutes read.

Program to Find Square Root of a Number Without sqrt Method in Java

The Java Math class sqrt () function can be used to determine the square root of a number. In this section, we'll write a Java program to find a number's...

3 minutes read.

Java Date add Days

In order to operate with the time and the Date in Java, we used the abstract Calendar class. It has several helpful interfaces that enable us to convert dates between...

4 minutes read.

Difference Between Access Specifiers and Modifiers in Java

Java employs access modifiers to restrict a class's data members, member functions, and constructor. Access modifiers are essential when creating Java program and applications. Access modifiers in Java include: defaultpublicprotectedprivate Default Access Modifiers Without...

4 minutes read.