## Intersection of two Linked Lists in Java

###### 2 years ago Lalit Bhagtani 0

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 Node createList(String[] dataArr){
Node node = null;
Node tempList = null;
for(String data : dataArr){
node = new Node();
node.setData(data);
tempList = node;
}else{
tempList.setNext(node);
tempList = node;
}
}
}

}
```

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;

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);
}

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;
}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) {
String[] firstListData = {"a","c","c","d"};
String[] secondListData = {"c","d","e","a"};