# Intersection of two linked lists in Java

In this post, we will discuss the topic, “Intersection of Two Linked Lists in Java”. Topic includes

1. How two linked lists can intersect to each other?
2. What will be the structure of linked lists after the intersection?
3. Real-world example to use the intersection of linked lists?
4. How can we identify the intersection point of two linked lists (Algorithm and Execution Process)?
5. 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:

1. Get the unsigned decimal difference of linked lists size of L1 & L2 (diff)
2. 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;
}

}
```

```package com.netSurfingZone.singlyLinkedList;

private int size = 0;
private Node<T> node;

public int size() {
return this.size;
}

/**
*
* @param 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++;
}

return;
}
Node<T> lastNode = getLastNode(node);
}

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;
return false;
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;

public Airport(String airportName, String airportId, String address) {
this.airportName = airportName;
this.airportId = airportId;
}

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;
}
}
}
@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 static void main(String[] args) {
commonRoute.add(new Airport("New York", "NYC", "United State" ));

route1.add(new Airport("New Delhi", "DEL", "India" ));
route1.add(new Airport("San Francisco", "SFO", "California" ));
System.out.println("Route1:" + route1 );
System.out.println(" ");

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

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:

**************************************************************************************