Single LinkedList - two LinkedLists are merging or not in java


In this Data structures tutorial we will try to find out whether two singly linkedLists are merging or not in java.
First, we will find out difference between size of two linkedLists, then iterate n number of nodes over larger list(where n is equal to difference, in our case difference is 1 and node we are going to reach in larger list will be 13), then iterate over both lists stepping forward one by one node until we find the common node. This has become very important linked list interview question.


Important methods used to find out whether two singly linkedLists are merging or not in java are as follows>
>twoListsAreMergingOrNot()

Logic explanation  to find out whether two singly linkedLists are merging or not in java with diagram >


example(considering above diagram) >
Difference between larger and smaller list  = 1.
Iterate 1 node over  larger list and reach 13.
Then start iterating over both lists and keep on comparing nodes, soon after few iterations we will find common node (i.e. 19) and hence it shows our lists are merging.

Full Program/SourceCode/Example to find out whether two singly linkedLists are merging or not in java >
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
 
 
 
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
public class LinkedListIntersectionPointExample {
public static void main(String[] args) {
   List<Integer> l1=new LinkedList<Integer>();
   List<Integer> l2=new LinkedList<Integer>();
  
   l1.add(11); l1.add(13); l1.add(16); l1.add(19); l1.add(22); l1.add(23);
                       l2.add(12); l2.add(14); l2.add(19); l2.add(22); l2.add(23);
  
   twoListsAreMergingOrNot(l1,l2);
}
public static void twoListsAreMergingOrNot(List<Integer> l1, List<Integer> l2){
   List<Integer> smallLinkedList=l1;
   List<Integer> largeLinkedList=l2;
   Integer diffInSize= l2.size()-l1.size();
   int ctr=0;
  
   if(diffInSize<0){   //if difference is negative, swap the references of lists.
          smallLinkedList=l2;
          largeLinkedList=l1;
          diffInSize=Math.abs(diffInSize);
   }
  
   Iterator<Integer> smallListIterator=smallLinkedList.iterator();
   Iterator<Integer> largeListIterator=largeLinkedList.iterator();
  
   while(largeListIterator.hasNext()){
          int listValue=largeListIterator.next();
          if(ctr<diffInSize){
                 ctr++;
                 continue;
          }
         
          if(listValue==smallListIterator.next()){
                 System.out.println("Lists are merging at :"+listValue);
                 return;
          }
   }
  
}
}
/* OUTPUT
Lists are merging at :19
*/


So in this Data structures tutorial we found solution to important and trending interview question whether two singly linkedLists are merging or not in java.


Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.


RELATED LINKS>

Stacks, Queues in java



Singly LinkedList implementations in java:-



Doubly LinkedList implementations in java:-



Some of the tricky and interesting Singly LinkedList implementations in java





Implement Stack, Queue using LinkedList.


No comments:

Post a Comment