Suppose you have two rail-roads modeled as linked list as shown in the figure below. The nodes are stations with names (A, B, etc.) and the links are direct path between the two stations. Write a complete Java program to find if these two rail-roads meet or not. If they happen to meet, then return the first common node where the meeting happens. If the rail-roads do not meet, then return null.

As shown in the figure below, the two rail-roads meet at station D since the 4^th station in the first rail-road is same as the 3^rd station in the second rail-road. So, station D should be returned.

Do not use Javas built-in HashMap or any other classes from the Collections framework.

You can start with the following code:

// see class LLStringNode on page 106 for the full implementation of linked list node.

public class StationNode

{

private String info;

private StationNode link;

}

public class RailroadTest {

// Implement this method

public StationNode findFirstCommonNode(StationNode road1, StationNode road2) { }

}

In the main method of RailroadTest class, test findFirstCommonNode method with the following scenarios:

For cases when both railroads have same length or not.

The railroads meet at the first station or last station.

The railroads meet at an arbitrary position.

Rail roads do not meet at all.

2 3