Intersection Point in Y Shaped Linked Lists in Java
Intersection Point in Y Shaped Linked Lists in Java
In this article, we are going to see how to find the intersection point in a Y-shaped linked list.
Method 1:
We need to find a common node of two linked lists. So we will insert all nodes of the first linked list into the HashSet, and then we will check the second linked list. We can do this using the following steps:
- Firstly, we will create an empty hash set.
- Then, we will traverse the entire first linked list and insert all node addresses in the hash set.
- After this, we will traverse the second linked list and check the node of the second linked list in the HashSet. If we find the common node, we will return that node.
Source code to implement method 1 in Java:
import java.util.*;
class Node
{
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class LinkedList_Intersection
{
Node head = null;
Node tail = null;
public void addToTheLast(Node node)
{
if (head == null) {
head = node;
tail = head;
}
else {
tail.next=node;
tail = node;
}
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
int n3 = sc.nextInt();
LinkedList_Intersection llist1 = new LinkedList_Intersection();
LinkedList_Intersection llist2 = new LinkedList_Intersection();
LinkedList_Intersection llist3 = new LinkedList_Intersection();
int a1=sc.nextInt();
Node head1= new Node(a1);
Node tail1= head1;
for (int i = 1; i < n1; i++)
{
int a = sc.nextInt();
tail1.next = (new Node(a));
tail1= tail1.next;
}
int b1=sc.nextInt();
Node head2 = new Node(b1);
Node tail2 = head2;
for (int i = 1; i < n2; i++)
{
int b = sc.nextInt();
tail2.next = (new Node(b));
tail2= tail2.next;
}
int c1=sc.nextInt();
Node head3= new Node(c1);
tail1.next = head3;
tail2.next = head3;
Node tail3 = head3;
for (int i = 1; i < n3; i++)
{
int c = sc.nextInt();
tail3.next = (new Node(c));
tail3= tail3.next;
}
Intersect obj = new Intersect();
Node temp=obj.intersectPoint(head1, head2);
if(temp==null)
System.out.println("No Intersection Found");
else
System.out.println("Intersection at-"+temp.data);
}
}
class Intersect
{
Node intersectPoint(Node head1, Node head2)
{
HashSet<Node> hs = new HashSet<Node>();
while (head1 != null) {
hs.add(head1);
head1 = head1.next;
}
while (head2!= null) {
if (hs.contains(head2)) {
return head2;
}
head2 = head2.next;
}
return null;
}
}
Output: -
In this output, the first line contains the total no of nodes in the first linked list. The second line contains the total number of nodes in the second linked list, and the third line contains the total number of nodes in the common linked list. Then, we will insert the elements for these three linked lists, respectively.
Time Complexity: O(N+M)
Auxiliary Space: O(N)
Method 2: Two-pointer Technique:
This method uses two pointers to return the common node with the help of the following steps:
- Initialize two pointers ptr1 and ptr2, at the head1 and head2.
- Traverse through the lists, one node at a time.
- When ptr1 reaches the end of a list, then redirect it to the head2.
- Similarly, when ptr2 reaches the end of a list, redirect it to the head1.
- Once both of them go through reassigning, they will be equidistant from the collision point.
- If at any node ptr1 meets ptr2, then it is the intersection node.
- After the second iteration, if there is no intersection node, it returns NULL.
Source code to implement method 2 in Java:
import java.util.*;
class Node
{
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class LinkedList_Intersection
{
Node head = null;
Node tail = null;
public void addToTheLast(Node node)
{
if (head == null) {
head = node;
tail = head;
}
else {
tail.next=node;
tail = node;
}
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
int n3 = sc.nextInt();
LinkedList_Intersection llist1 = new LinkedList_Intersection();
LinkedList_Intersection llist2 = new LinkedList_Intersection();
LinkedList_Intersection llist3 = new LinkedList_Intersection();
int a1=sc.nextInt();
Node head1= new Node(a1);
Node tail1= head1;
for (int i = 1; i < n1; i++)
{
int a = sc.nextInt();
tail1.next = (new Node(a));
tail1= tail1.next;
}
int b1=sc.nextInt();
Node head2 = new Node(b1);
Node tail2 = head2;
for (int i = 1; i < n2; i++)
{
int b = sc.nextInt();
tail2.next = (new Node(b));
tail2= tail2.next;
}
int c1=sc.nextInt();
Node head3= new Node(c1);
tail1.next = head3;
tail2.next = head3;
Node tail3 = head3;
for (int i = 1; i < n3; i++)
{
int c = sc.nextInt();
tail3.next = (new Node(c));
tail3= tail3.next;
}
Intersect obj = new Intersect();
Node temp=obj.intersectPoint(head1, head2);
if(temp==null)
System.out.println("No Intersection Found");
else
System.out.println("Intersection at-"+temp.data);
}
}
class Intersect
{
Node intersectPoint(Node head1, Node head2)
{
Node curr1 = head1, curr2 = head2;
while (curr1 != curr2)
{
if (curr1 == null)
{
curr1 = head2;
}
else
{
curr1 = curr1.next;
}
if (curr2 == null)
{
curr2 = head1;
}
else
{
curr2 = curr2.next;
}
}
return curr1;
}
}
Output: -
Time Complexity: O(N+M)
Auxiliary Space: O(1)