Intersection of Two Linked Lists 1

The linked list L1 is  (1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 4 -> 5 -> 6) having a length n and linked list L2 is (-1 -> -3 -> 9 -> 4 -> 5 -> 6) having a length m.

So above both L1 and L2 are intersecting at node 9. So now how to find this.

We will be taking the Diff approach.

First take the difference of two linked list. i.e. length difference . Like it came 4 , then we can jump as much as difference at once in the longer linked list. Like we can jump 4 nodes directly in the longer linked list. After that we will iterate over the two linked list simultaneously to find the common node.
Below is the java Program to find the same.
package com.algo.intersection.linkedlist;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class FindIntersection {

 public static final List<Integer> listOne = new LinkedList<Integer>(){
 {
  add(1);
  add(2);
  add(3);
  add(7);
  add(8);
  add(9);
  add(4);
  add(5);
  add(6);
 }
};
 public static final List<Integer> listTwo = new LinkedList<Integer>(){
 {
  add(-1);
  add(-3);
  add(9);
  add(4);
  add(5);
  add(6);
 }
};

// so at above the intersection point is at node value 9

 public  static Integer findIntersectionPoint(){

  List<Integer> biggerList = listTwo;
  List<Integer> smallerList = listOne;

  int diffInSize = listTwo.size() - listOne.size();
  int count = 0;

  // if diffInSize is negative then interchange the references.
  if(diffInSize < 0){
   biggerList = listOne;
   smallerList = listTwo;
   diffInSize = Math.abs(diffInSize);
  }

  Iterator<Integer> two = smallerList.iterator();

  for(Integer one : biggerList){
   if(count < diffInSize){
    count ++;
    continue;
   }
   if(one == two.next())
    return one;
   }

  return null;
 }

 public static void main(String[] args) {
  System.out.println(findIntersectionPoint());
 }

}

By this we are eliminating the extra size of the longer list and now the resultant two
lists are of same length.

One comment on “Intersection of Two Linked Lists

  1. Reply Daniel Beaulieu Aug 26,2013 7:52 pm

    “Appreciate you sharing, great article post.Truly thank you! Excellent.”

Leave a Reply