Intersection of two linked lists

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

  1. How two linked list 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:

Input: linked list L1 & linked list L2

  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:

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 equality of nodes.

Now, we will see the logic implemented in JAVA to identify the intersection of two linked list.[Try Yourself]

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.

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.

 

 

 

Below is the logic to identify the intersection point of two linked list.

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]

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

 

Hope you like this post. Please leave your comments/suggestions.

 

You may like –

Top