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