Write a java code, Suppose you have two rail-roads modeled as linked list as sho

Question

Write a java code, 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 4th station in the first rail-road is same as the 3rd station in the second rail-road. So, station D should be returned.

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

For cases when both railroads have same length or not.

1. The railroads meet at the first station or last station.

2. The railroads meet at an arbitrary position.

3. Rail roads do not meet at all.

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

I started with this code but am having trouble finishing it

public class StationNode {

private String info;

private StationNode link;

}

public class RailroadTest {

   // Implement this method

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

}

Explanation / Answer

import java.io.*;

class StationNode {
    private String info;
    private StationNode link;
    public void setInfo(String a){
          info = a;
     }
     public void setLink(StationNode a){
            link = a;
     }
     public String getInfo(){
          return info;
     }
     public StationNode getLink(){
            return link;
     }
}

public class RailroadTest{

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

           StationNode s1, s2, s3;
           s1 = road1;
           s2 = road2;
           int found = 0;
           s3 = null;
           while (s1 != null){
               s2 = road2;
               while(s2!=null) {
                  if (s2.getInfo().equals(s1.getInfo())){
                      s3 = s1;
                     found = 1;
                     break;
                  }
                  s2 = s2.getLink();
               }
               s1 = s1.getLink();
              if (found == 1)
                 break;
           }
           while (s2 != null){
               s1 = road1;
               while(s1!=null) {
                  if (s1.getInfo().equals(s2.getInfo())){
                     s3 = s2;
                     found = 1;
                     break;
                  }
                  s1 = s1.getLink();
               }
               s2 = s2.getLink();
              if (found == 1)
                 break;
           }

              return s3;
   }

   public static void main(String[] args){

        StationNode A,B, C;

        A = null;
        B= null;
        C = null;
        StationNode a1 = new StationNode();
        a1.setInfo("a1");
        StationNode a2 = new StationNode();
        a2.setInfo("a2");
        StationNode a3 = new StationNode();
        a3.setInfo("a3");
        StationNode a4 = new StationNode();
        a4.setInfo("a4");

        A = a1;
        a1.setLink(a2);
        a2.setLink(a3);
        a3.setLink(a4);
        a4.setLink(null);

        StationNode b1 = new StationNode();
        b1.setInfo("b1");
        StationNode b2 = new StationNode();
        b2.setInfo("b2");
        StationNode b3 = new StationNode();
        b3.setInfo("b3");
        StationNode b4 = new StationNode();
        b4.setInfo("b4");

        B = b1;
        b1.setLink(b2);
        b2.setLink(b3);
        b3.setLink(b4);
        b4.setLink(null);

       
        C = findFirstCommonNode(A,B);
       
        if (C == null){
           System.out.println("They don't meet");
        }
        else {
           System.out.println("They meet at " + C.getInfo());
        }
       
        b4.setLink(a4);

        C = findFirstCommonNode(A,B);
        if (C == null){
           System.out.println("They don't meet");
        }
        else {
           System.out.println("They meet at " + C.getInfo());
        }

        b4.setLink(a1);

        C = findFirstCommonNode(A,B);
        if (C == null){
           System.out.println("They don't meet");
        }
        else {
           System.out.println("They meet at " + C.getInfo());
        }
       
        b4.setLink(null);
        b2.setLink(a3);
        C = findFirstCommonNode(A,B);
        if (C == null){
           System.out.println("They don't meet");
        }
        else {
           System.out.println("They meet at " + C.getInfo());
        }
        
       
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.