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

PriorityQueue in Java

PriorityQueue in Java A PriorityQueue is a member of the Java Collection Framework and is used when the values are needed to be processed based on priority. Priority queue operates similar to...

8 minutes read.

Java Thread Creation

Java provides the two ways to create a Thread: Implementing the Runnable interface.Extending the Thread class. Implementing Runnable interface The easiest way of creating a thread is to make a class that implements...

5 minutes read.

Java Open File

Java Desktop class give an open() strategy to open a filr. It has a place with a java.awt package. Work area execution is stage subordinate, so it is important to...

5 minutes read.

String to JSON in Java

Nowadays, receiving data in JSON String format rather than XML is quite frequent. Java does not transform JSON String to JSON Object when dealing with JSON String. However, using the...

3 minutes read.

Heap Implementation in Java

The root node or parent node of a Java heap is compared to its left and right offspring, and the children are then ordered in line with the comparison.Assuming that...

9 minutes read.

Multithreading in Java

Multithreading is a specialized form of multitasking. It is responsible for executing more than one task at a time of a single program, and each task is a separate thread. A program...

8 minutes read.

Java String getBytes() method

getBytes() method returns sequence of bytes. Syntax: There are three variants of getBytes() method: public byte[] getBytes()        public byte[] getBytes(String charsetName) public byte[] getBytes(Charset charset) Returns: It returns sequence of bytes. Java String getBytes() Example...

2 minutes read.

Java Font

The font is a Java class that is a part of java.awt package. The Serializable interface is implemented by it. The direct recognized child of a Java Font class is...

8 minutes read.

Java Math round() Method

The round() method of Java Math class returns a long or an int value that is closest to the argument and is rounded to positive infinity. Syntax: public static int round(float a)public...

2 minutes read.

Two Decimal Places Java

When a double data type is used in Java before a variable, this indicates 15 digits after decimal point. However, there are situations when we only require 2 decimal places...

4 minutes read.

Types of Events in Java

One of Java's key ideas is the principle of an event. Events in Java are activities that result in a change in the state or behavior of an object. The...

4 minutes read.

How to find the length of an Array in Java

Arrays: An array is a sort of container object that stores constant quantities of values of a single type in one memory area. A finite number of items must all be...

3 minutes read.

Find next greater number with same set of digits in Java

It contains a number (num). Finding the smallest number that has the same number of elements as num that is also larger than num is the task at hand. If...

8 minutes read.

Java Math tan() Method

The tan() method of Java Math class returns the trigonometric tangent of the specified angle. Syntax: public static double tan(double a) Parameters: The parameter ‘a’ represents an angle measured in radians. Return Value: The tan() method...

2 minutes read.

Kong Java Client

Kong is an Organization Microservice Programming interface gateway. Kong gives an adaptable deliberation layer that safely oversees correspondence among clients and microservices by means of a Programming interface. Otherwise called...

6 minutes read.

Balanced Prime Number in Java

This section will cover the definition of a balanced prime number as well as how to find one using a Java program. Balance Prime Number A prime number that is equivalent to...

5 minutes read.

Bifunction in java 8

A functional interface in Java is called BiFunction. It first appeared in Java 8. It can serve as the assigning target for a method reference or lambda expression. The java.util.function...

4 minutes read.

Thread States in Java

An Item's Life Cycle (Thread States) A thread can be in any of the states mentioned above at any given time in Java. They are as follows: New Active I'm blocked or waiting Temporary...

3 minutes read.

Loose Coupling in Java

Loosely coupling mechanism in java means one reference of a variable capable of holding multiple implementation class memory is called loosely coupling. Or in other words, one interface reference variable...

3 minutes read.

HashMap Vs HashTable

HashMap HashMap is the basic implementation of the map interface in Java. HashMap stores the data in key and value pairs. Keys are used to access the value of the element. It...

5 minutes read.