Code Destine

Intersection of two Linked Lists in Java :- 

You have given two linked list, create a linked list containing elements that are same in both linked list excluding duplicates. i.e. create intersection of two given linked list. Order of elements in new linked list does not matter.

You can see union here, Union of two Linked Lists in Java

Algorithm :- 

The algorithm for the implementation of this problem is very simple, here are steps :- 

1. Create a new HashMap.
2. Traverse second linked list and store data of each node in a map as a key and false (Boolean) as a value.
3. Traverse first linked list, check if data (data stored in the node) is present in a map (as a key) and its value is false. if it is present then we create a new node with that data, add it to the new linked list and update its value to true in map. Otherwise continue.

Example of Intersection of two Linked Lists in Java :- 

1) Create a class Node, this class will be a node of our linked list.

package com.codedestine.algorithm.linkedlist;

public class Node {

  private String data;
  private Node next;
 
  public String getData() {
    return data;
  }

  public void setData(String data) {
    this.data = data;
  }

  public Node getNext() {
    return next;
  }

  public void setNext(Node next) {
    this.next = next;
  }
 
}

2) Create a class CreateLinkedList, this class has a method createList which takes string array as an argument and return linked list.

package com.codedestine.algorithm.linkedlist;

public class CreateLinkedList {
 
  public Node createList(String[] dataArr){
    Node listHead = null;
    Node node = null;
    Node tempList = null;
    for(String data : dataArr){
      node = new Node();
      node.setData(data);
      if(listHead == null){
        listHead = node;
        tempList = node;
      }else{
        tempList.setNext(node);
        tempList = node;
      }
    }
    return listHead;
  }

}

3) Create a class IntersectionLinkedList, this class has a method intersection which takes two linked list as an argument and return intersection linked list.

package com.codedestine.algorithm.linkedlist;

import java.util.HashMap;
import java.util.Map;

public class IntersectionLinkedList {

   private Node intersectionListHeadNode;
 
   private Map<String,Boolean> getAllDataOfList(Node list){
     Map<String,Boolean> uniqueMap = new HashMap<String,Boolean>();
     while(list != null){
       uniqueMap.put(list.getData(),false);
       list = list.getNext();
     }
     return uniqueMap;
   }

   public Node intersection(Node firstList, Node secondList){ 
     Map<String,Boolean> uniqueMap = getAllDataOfList(secondList);
     addList(firstList,uniqueMap);
     return this.intersectionListHeadNode;
   }
 
   private void addList(Node sourceList,Map<String,Boolean> uniqueMap){
     Node tempNode = null;
     Node tempList = null;
     while(sourceList != null){
       if(uniqueMap.containsKey(sourceList.getData()) && !uniqueMap.get(sourceList.getData())){
         uniqueMap.put(sourceList.getData(), true);
         tempNode = createNode(sourceList.getData());
         if(tempList == null){ 
           tempList = tempNode;
           this.intersectionListHeadNode = tempList;
         }else{
           tempList.setNext(tempNode);
           tempList = tempNode;
         } 
       }
       sourceList = sourceList.getNext(); 
     }
   }
 
   private Node createNode(String data){
     Node node = new Node();
     node.setData(data);
     return node;
   }
 
}

4) Create a class Main, this class will be our demo class.

package com.codedestine.algorithm.linkedlist;

public class Main {

   public static void main(String[] args) {
     CreateLinkedList createLinkedList = new CreateLinkedList();
     String[] firstListData = {"a","c","c","d"};
     Node firstList = createLinkedList.createList(firstListData);
     String[] secondListData = {"c","d","e","a"};
     Node secondList = createLinkedList.createList(secondListData);
  
     IntersectionLinkedList intersectionLinkedList = new IntersectionLinkedList();
     Node intersectionList = intersectionLinkedList.intersection(firstList, secondList);
 
     while(intersectionList != null){
       System.out.println(intersectionList.getData());
       intersectionList = intersectionList.getNext();
     } 
   }

}

Result :- 

That’s all for Intersection of two Linked Lists in Java, If you liked it, please share your thoughts in a comments section and share it with others too.