content: package linkedlist;
  
  
  public class IntersectionPoints {
  
  
      /*
       * Given head nodes of two linked lists that may or may not intersect,
       * find out if they intersect and return the point of intersection;
       * return null otherwise.
       * Eg: Input:  29 -> 23 -> 82 -> 11, 12, 17
       *             13 -> 4 -> 12 -> 17
       *     Output: 12
       *
       * */
      public static class LinkedList {
  
          public static Node head1, head2;
  
          static class Node {
  
              int data;
              Node next;
  
              Node(int d) {
                  data = d;
                  next = null;
              }
          }
  
          /*function to get the intersection point of two linked
          lists head1 and head2 */
          int getNode() {
              int c1 = getCount(head1);
              int c2 = getCount(head2);
              int d;
  
              if (c1 > c2) {
                  d = c1 - c2;
                  return getIntersectionNode(d, head1, head2);
              } else {
                  d = c2 - c1;
                  return getIntersectionNode(d, head2, head1);
              }
          }
  
          /* function to get the intersection point of two linked
           lists head1 and head2 where head1 has d more nodes than
           head2 */
          private int getIntersectionNode(int d, Node node1, Node node2) {
              int i;
              Node current1 = node1;
              Node current2 = node2;
              for (i = 0; i < d; i++) {
                  if (current1 == null) {
                      return -1;
                  }
                  current1 = current1.next;
              }
              while (current1 != null && current2 != null) {
                  if (current1.data == current2.data) {
                      return current1.data;
                  }
                  current1 = current1.next;
                  current2 = current2.next;
              }
  
              return -1;
          }
  
          /*Takes head pointer of the linked list and
          returns the count of nodes in the list */
          private int getCount(Node node) {
              Node current = node;
              int count = 0;
  
              while (current != null) {
                  count++;
                  current = current.next;
              }
  
              return count;
          }
      }
  
  
      public static void main(String[] args) {
          LinkedList list = new LinkedList();
  
  
          list.head1 = new LinkedList.Node(3);
          list.head1.next = new LinkedList.Node(6);
          list.head1.next.next = new LinkedList.Node(15);
          list.head1.next.next.next = new LinkedList.Node(15);
          list.head1.next.next.next.next = new LinkedList.Node(30);
  
  
          list.head2 = new LinkedList.Node(10);
          list.head2.next = new LinkedList.Node(15);
          list.head2.next.next = new LinkedList.Node(30);
  
          System.out.println("The node of intersection is " + list.getNode());
  
      }
  }
  
  
  
  
  