In this post, we will discuss the topic, “Intersection of Two Linked Lists in Java”. Topic includes
- How two linked lists can intersect to each other?
- What will be the structure of linked lists after the intersection?
- Real-world example to use the intersection of linked lists?
- How can we identify the intersection point of two linked lists (Algorithm and Execution Process)?
- Write a JAVA function to identify the intersection point of two linked lists.
When two linked lists have common tails, means if two linked lists have the same linked nodes(same data and next node), this situation is called the intersection of two linked lists. Below is the structure of two linked lists after the intersection.
Now we can think about the real world application of the intersection of two linked list. We will take the example of long-distance flights where the flight has multiple layovers between departure and destination location. Suppose, one AirIndia flight has the route :
Bangalore(BLR)—->New Delhi (DEL)—>San Francisco (SFO)—>Denver (DEN)—> New York(NYC) .
Another AirIndia flight has the route :
Mumbai(BOM)—>Dubai(DXB)–>Denver(DEN)—>New York(NYC)
To optimize the flight cost, AirIndia wants to merge these two flights at any particular airport. To implement this business scenario, first, we should create the linked list for each route and then need to find out the intersection point of these two routes. As explained before, Denver(DEN) will be the intersection point of these two flight routes.
We will keep above scenario to implement the function which will identify the intersection point of two linked lists.
Algorithm:
Input: linked list L1 & linked list L2
- Get the unsigned decimal difference of linked lists size of L1 & L2 (diff)
- If linked list L1 size is more than the size of linked list L2
- Compare node of L1 at index “diff” with the node of L2 at index 0. If both nodes are equals then the intersection node will be the node of L1 at index “diff”. No need to check further.If not,
- Compare the node of L1 at index “diff +1 ” with the node of L2 at index 1. If both nodes are equals then the intersection node will be the node of L1 at index “diff + 1”.No need to check further.
- Repeat the above check till the end of the two linked lists.
3. If linked list L2 size is more than the size of linked list L1
- Compare node of L2 at index “diff” with the node of L1 at index 0. If both nodes are equals then the intersection node will be the node of L2 at index “diff”. No need to check further.If not,
- Compare the node of L2 at index “diff +1 ” with the node of L1 at index 1. If both nodes are equals then the intersection node will be the node of L2 at index “diff + 1”.No need to check further.
- Repeat the above check till the end of the two linked lists.
Execution Process:
[stextbox id=’info’]Here, we need to understand the meaning of equality of nodes. If two nodes are equals, it means, the data on both nodes should be equal and the next node addresses of two nodes should also be equal. We can not just compare the data or next addresses alone for the equality of nodes.[/stextbox]
Now, we will see the logic implemented in JAVA to identify the intersection of two linked list.[Try Yourself]
Intersection of two linked lists in Java Example
Below is the Node.class. See the implementation of equals() and hasCode() method implementation. If data and next node address of two nodes are equals, then those two nodes will be equal.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
Below is the SinglyLinkedList class where we have overloaded “add” operations to add data at the end of the linked list and also directly add any linked list.
package com.netSurfingZone.singlyLinkedList;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
public int size() {
return this.size;
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
public void add( SinglyLinkedList<T> linkedList) {
if(linkedList == null || linkedList.node == null) {
return;
}
Node<T> lastNode = getLastNode(node);
lastNode.setNode(linkedList.node);
size= size + linkedList.size();
}
public Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
package com.study.DTO;
public class Airport {
private String airportName;
private String airportId;
private String address;
public Airport(String airportName, String airportId, String address) {
this.airportName = airportName;
this.airportId = airportId;
this.address = address;
}
public String getAirportName() {
return airportName;
}
public void setAirportName(String airportName) {
this.airportName = airportName;
}
public String getAirportId() {
return airportId;
}
public void setAirportId(String airportId) {
this.airportId = airportId;
}
public String getAddress() {
return address;
}
public void setAddress(String address) {
this.address = address;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((airportId == null) ? 0 : airportId.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Airport))
return false;
Airport other = (Airport) obj;
if (airportId == null) {
if (other.airportId != null)
return false;
} else if (!airportId.equals(other.airportId))
return false;
return true;
}
@Override
public String toString() {
return "Airport [airportName=" + airportName + ", airportId=" + airportId + ", address=" + address + "]";
}
}
Below is the logic to identify the intersection point of two linked list.
package com.netSurfingZone.singlyLinkedList;
import com.study.DTO.Airport;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Airport> commonRoute=new SinglyLinkedList<Airport>();
commonRoute.add(new Airport("Denver", "DEN", "Colorado" ));
commonRoute.add(new Airport("New York", "NYC", "United State" ));
SinglyLinkedList<Airport> route1=new SinglyLinkedList<Airport>();
route1.add(new Airport("Bangalore", "BLR", "India" ));
route1.add(new Airport("New Delhi", "DEL", "India" ));
route1.add(new Airport("San Francisco", "SFO", "California" ));
route1.add(commonRoute);
System.out.println("Route1:" + route1 );
System.out.println(" ");
SinglyLinkedList<Airport> route2=new SinglyLinkedList<Airport>();
route2.add(new Airport("Mumbai", "BOM", "India" ));
route2.add(new Airport("Dubai", "DXB", "UAE" ));
route2.add(commonRoute);
System.out.println("Route2:" + route2 );
System.out.println(" ");
/**
* Route1:
* Bangalore(BLR)---->New Delhi (DEL)--->San Francisco (SFO)--->Denver (DEN)---> New York(NYC) .
*
* Route2:
* Mumbai(BOM)--->Dubai(DXB)-->Denver(DEN)--->New York(NYC)
*/
Airport intesectionAirport=intersectionPoint(route1,route2);
System.out.println("Intersection : " + intesectionAirport);
}
private static Airport intersectionPoint(SinglyLinkedList<Airport> route1, SinglyLinkedList<Airport> route2) {
Airport intersectionPoint=null;
Integer lengthOfFist= route1.size();
Integer lengthOfSecond= route2.size();
Integer difference=lengthOfFist-lengthOfSecond;
if(difference < 0 ) {
difference=Integer.parseInt(Integer.toUnsignedString(difference));
}
boolean isFirstSizeMore=false;
boolean isSecondSizeMore=false;
if(route1.size() > route2.size()) {
isFirstSizeMore=true;
}
else if(route1.size() < route2.size()) {
isSecondSizeMore=true;
}
else {
isFirstSizeMore=true;
}
if(isFirstSizeMore) {
for (int i = difference , j= 0 ; i < route1.size() & j < route2.size(); i++ ,j++) {
if(route1.getNode(i).equals(route2.getNode(j))){
intersectionPoint=route1.getNode(i).getData();
break;
}
}
}
if(isSecondSizeMore) {
for (int i = difference , j= 0 ; i < route2.size() & j < route1.size(); i++ ,j++) {
if(route2.getNode(i).equals(route1.getNode(j))){
intersectionPoint=route2.getNode(i).getData();
break;
}
}
}
return intersectionPoint;
}
}
Result:
**************************************************************************************
Route1:[Airport [airportName=Bangalore, airportId=BLR, address=India],Airport [airportName=New Delhi, airportId=DEL, address=India],Airport [airportName=San Francisco, airportId=SFO, address=California],Airport [airportName=Denver, airportId=DEN, address=Colorado],Airport [airportName=New York, airportId=NYC, address=United State]]
Route2:[Airport [airportName=Mumbai, airportId=BOM, address=India],Airport [airportName=Dubai, airportId=DXB, address=UAE],Airport [airportName=Denver, airportId=DEN, address=Colorado],Airport [airportName=New York, airportId=NYC, address=United State]]
Intersection : Airport [airportName=Denver, airportId=DEN, address=Colorado]
**************************************************************************************
That’s all about Intersection of two linked lists in Java. Please leave your comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Reverse of Singly Linked List.
- Implementation of Index based Linked List.
- Merge sort for Linked List in Java
- Rotation of Linked List.
- Iterator for singly linked list java.
LinkedList Java docs.
Summary – We have seen Intersection of two linked lists in Java with example.
